摘要：記一次優(yōu)惠券最優(yōu)使用算法先說一下業(yè)務(wù)背景。公司做的一個(gè)投資的，投資金額可以用優(yōu)惠券抵扣。但是無法獲取具體使用了哪張優(yōu)惠券簡(jiǎn)單就是很難獲得優(yōu)惠券的窮舉法數(shù)據(jù)太多，不可控。但是這種面額的優(yōu)惠券出現(xiàn)幾率幾乎沒有請(qǐng)教期待有大神給出更好的算法

先說一下業(yè)務(wù)背景。公司做的一個(gè)投資的APP，投資金額可以用優(yōu)惠券抵扣。紅包面額（100，50，30，10）

優(yōu)先使用大面額的紅包，即優(yōu)先使用張數(shù)最少的紅包組合

優(yōu)先使用有限制的紅包，即優(yōu)先使用有限制紅包張數(shù)占比最大的組合

優(yōu)先使用即將過期的紅包，即優(yōu)先使用平均有效期最短的組合

選擇紅包面額之和最大的組合（面額總值≤投資額*1%）

前面三個(gè)都可以通過數(shù)據(jù)庫(kù)檢索排序?qū)崿F(xiàn)生成一個(gè)數(shù)組，最后一個(gè)就要使用程序算法實(shí)現(xiàn)了。
一開始有想過背包法、窮舉法。

背包法：說實(shí)在的，沒看懂（比較尷尬），實(shí)現(xiàn)是可以實(shí)現(xiàn)。但是無法獲取具體使用了哪張優(yōu)惠券(簡(jiǎn)單就是很難獲得優(yōu)惠券的Id)

窮舉法：數(shù)據(jù)太多，不可控。

算出用戶本次投資最大使用優(yōu)惠券總額（redAmount）、獲取用戶的優(yōu)惠券列表(redCoupons)（已按前三規(guī)則排序）直接上代碼:

    public function dealCoupon()
    {
        $redCoupons =[]; $restRedAmount = 100;

        $redCouponIdLists = []; $restRedAmounts = [];
        $arrCount = count($redCoupons);
        for ($i=0; $i<$arrCount; $i++) {
            list($redCouponIdList, $restRedAmount) = getBestCoupon($redCoupons, $restRedAmount);
            if ($restRedAmount == 0) {
                $bestCouponIdList = $redCouponIdList;
                break;
            }

            $redCouponIdLists[] = $redCouponIdList;
            $restRedAmounts[] = $restRedAmount;
            array_shift($redCoupons);
        }

        if (empty($bestCouponIdList)) {
            $pos = array_search(min($restRedAmounts), $restRedAmounts);
            $bestCouponIdList = $redCouponIdLists[$pos];
        }

    }

    /**
     * 紅包最優(yōu)算法
     */
    private function getBestCoupon($redCoupons, $restRedAmount)
    {
        $redCouponAmount = 0;
        foreach ($redCoupons as $redCoupon) {
            if ($restRedAmount >= $redCoupon->getAmount()) {
                $redCouponAmount   = $redCouponAmount + $redCoupon->getAmount());
                $redCouponIdList[] = $redCoupon->getCouponId();
                $restRedAmount     = $restRedAmount - $redCoupon->getAmount();

                if ($restRedAmount == 0) break;
            }
        }

        return [$redCouponIdList, $restRedAmount];
    }

用50塊嘗試，最多80

用第一個(gè)30嘗試，最多90，已經(jīng)最優(yōu)，中斷程序（否則繼續(xù)向下類推）

因?yàn)槊看嗡阃昃桶言摷t包從數(shù)組中推出，這樣還是存在問題。例如投資1600，用戶有（100，50，30，30）。這樣就不會(huì)出現(xiàn)最優(yōu)。

不把計(jì)算過優(yōu)惠券推出，需要每次把要計(jì)算那張優(yōu)惠券多帶帶拿出來

這樣程序復(fù)雜了很多，但還是可以實(shí)現(xiàn)的

這樣還是會(huì)出現(xiàn)算法1.0的問題，不過這種按照順序取優(yōu)惠券很難不出現(xiàn)問題。但是這種面額的優(yōu)惠券出現(xiàn)幾率幾乎沒有

期待有大神給出更好的算法