【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;
}



?>