PHP 动态规划算法

//初始化各个物品重量和价值数组
//                  a ,b,  c, d, e   
$weight_arr = array(4,  2, 6, 5, 3);
$value_arr = array(6,  3,  5, 4, 6);

//设置包最大重量为10
$bag_max = 10;
$items = count($weight_arr) - 1;
//中间的各种决策(依次放入物品a,b,c,d,e)
function dynamic($bag_max, $items, $weight_arr, $value_arr)
{
    $cache_map = [];
    for ($i = 1; $i <= $bag_max; $i++){
        for ($j = 1; $j <= $items; $j++) {
            $weight = $weight_arr[$j];
            $value = $value_arr[$j];
            $prev_value = (int)$cache_map[$j - 1][$i];
            if ($weight < $i) {
                $cache_map[$j][$i] = $prev_value;
            } else {
                $extra_value = $value + $cache_map[$j - 1][$i - $weight];
                $cache_map[$j][$i] = max($prev_value, $extra_value);
            }
        }
   }
    //最终状态
    for ($i = 1; $i <= $bag_max; $i++) {
        echo $i . ':' . $cache_map[$items][$i] . PHP_EOL;
    }
}