【PHP】演算法，獲取給定值的最優組合：虛擬幣抵扣問題解決方案

商城裡邊。虛擬幣抵扣問題解決方案

虛擬幣抵扣規則，按照以下規則執行：

1.如果一個訂單包含多款商品，且均支持虛擬幣抵扣時：

優先按照最大化使用虛擬幣進行全額抵扣原則進行抵扣，若抵扣後用戶虛擬幣賬號仍有餘額可以使用，且仍有未抵扣的商品，則繼續抵扣剩餘未抵扣商品中最小抵扣額度的商品；

示例：

1）用戶虛擬幣賬戶餘額650，下單購買5款商品（A、B、C、D、E），5款商品分別可抵扣最大金額為（A->100，B->200，C->300，D->400，E->500）此時抵扣結果為：

優先全額抵扣A、E 兩款商品，

再抵扣B款商品50個虛擬幣，50個虛擬幣可抵扣的商品金額，根據後端設置進行比例計算，小數點保留2位 （捨去法，不進行四捨五入）

2）用戶虛擬幣賬戶餘額60，下單購買5款商品（A、B、C、D、E），5款商品分別可抵扣最大金額為（A->100，B->200，C->300，D->400，E->500）此時抵扣結果為：

優先全額抵扣商品不存在，

則直接抵扣A款商品60個虛擬幣，60個虛擬幣可抵扣的商品金額，根據後端設置進行比例計算，小數點保留2位（捨去法，不進行四捨五入）

3）用戶虛擬幣賬戶餘額2000，下單購買5款商品（A、B、C、D、E），5款商品分別可抵扣最大金額為（A->100，B->200，C->300，D->400，E->500）此時抵扣結果為：

優先全額抵扣A、B、C、D、E 所有商品，

4）用戶虛擬幣賬戶餘額0，下單購買5款商品（A、B、C、D、E），5款商品分別可抵扣最大金額為（A->100，B->200，C->300，D->400，E->500）此時抵扣結果為：

不用抵扣

代碼例子如下，如有需要，可根據實際場景修改使用

<?php $result_flb = array( array(id=>1,currency => 15,cash => 2,), array(id=>2,currency => 20,cash => 2), array(id=> 3,currency => 10,cash => 2), array(id=> 4,currency => 6,cash => 10), ); $arr = array_column($result_flb,currency); //循環取出,轉化成floor類型 foreach($arr as &$v){ $v = floor($v); } unset($v); $max = 4; $re = digui($arr); foreach ($re as $key => $value) { if ($key <= $max) { isset($result) || $result = [$key, $value]; if ($key > $result[0]) { $result = [$key, $value]; } } } isset($result) || $result = [0, []]; $arr_yes = array(); //滿足條件的集合 $arr_no = array(); //不滿足條件的集合 foreach($result_flb as $k=>$v){ if(in_array(floor($v[currency]),$result[1])){ $arr_yes[$k]=$v; $arr_yes[$k][bili]=100; }else{ $arr_no[$k]=$v; } } $arr_no = array_sort($arr_no); $fine_money = $result[0]; if(empty($arr_no)){ $finally = $fine_money; }else{ $bilie = $arr_no[currency] / $arr_no[cash]; $bilie_money =intval(($max-$fine_money)/$bilie * pow(10, 2))/ pow(10, 2) ;// 捨去小數點取整: 不使用四捨五入 $finally = $fine_money + $bilie_money; $arr_no[bili] = $bilie*100; } $he_no[0] = $arr_no; $res = array_merge_recursive($arr_yes,$he_no); echo $finally; //最終結果 function array_sort($arr_no){ // 裝入臨時數組 $cur = array(); foreach ($arr_no as $key => $value) { $cur[$value[id]] = $value[currency]; } // 臨時數組排序 sort($cur); // 原數組排序、取值 $result = array(); foreach ($arr_no as $key => $value) { switch ($value[currency]) { case $cur[0]: $result = $value; break; } } return $result; }function digui($arr, $re = []) { if (count($arr) == 0) { return []; } if (count($arr) == 1) { $re[$arr[0]] = [$arr[0]]; } if (count($arr) >= 2) { $x = array_shift($arr); $re[$x] = [$x]; for ($b = 0; $b < count($arr); $b++) { $result = $x + $arr[$b]; $re[$result] = [$x, $arr[$b]]; } $re = digui($arr, $re); foreach ($re as $k => $v) { if (!in_array($arr[0], $v)) { array_unshift($v, $arr[0]); $re[$arr[0] + $k] = $v; } } } return $re;}?>

貪婪演算法的動態規劃也可以解決。但是基於實際場景。總會出各種奇葩的需求出來。所以我就把這個方法給廢棄了。下邊是一位朋友貢獻的演算法。

（藍洛提供，博客地址： http://www.zhaorui.info）

缺點就是： 當你給定值數值較大時，就會內存溢出

<?php ini_set(error_reporting,E_ALL^E_NOTICE); $arr2 = array( 0 => array( id=>1, cur => 15, cash => 2 ), 1 => array( id=>2, cur => 20, cash => 2 ), 2 => array( id=> 3, cur => 10, cash => 2 ), 3 => array( id=> 4, cur => 6.2, cash => 10 ), ); $arr = array_column($arr2,cur); //循環取出,轉化成整數類型 foreach($arr as &$v){ $v = intval($v); } print_r($arr); unset($v);$maxSize = floor(23.6);//此處填寫要的值//$arr = array(15, 20, 10, 6,30,5,1,13,17,9);$result = array();$answers = array();$currSize = floor(23.6);//此處也填寫要的值$len = count($arr);for ($i = 0; $i < $len; $i++) { $result[] = array(); for ($j = 0; $j <= $maxSize; $j++) { $result[$i][$j] = 0; }}//var_dump($result);die;for ($i = 0; $i <= $maxSize; $i++) { for ($j = 0; $j < $len; $j++) { if ($arr[$j] > $i) { if ($j === 0) $result[$j][$i] = 0; else $result[$j][$i] = $result[$j - 1][$i]; } else { if ($j === 0) $result[$j][$i] = $arr[$j]; else $result[$j][$i] = max($result[$j - 1][$i], $result[$j - 1][$i - $arr[$j]] + $arr[$j]); } }}// 找出答案for ($i = $len - 1; $i >= 0 && $currSize !== 0; $i--) { if ($result[$i][$currSize] - $result[$i - 1][$currSize - $arr[$i]] === $arr[$i]) { $answers[] = $arr[$i]; $currSize -= $arr[$i]; }}print_r($answers);$arr3 = array();foreach($arr2 as $k=>$v){ if(in_array(intval($v[cur]),$answers)){ $arr3[$k]=$v; }}print_r($arr3);

如有更好的辦法，歡迎指導！