PHP实现动态规划之背包问题

由于我司举办一个算法编程大赛，随机抽签下面图片的算法题目，想了一段时间记起之前在书（算法图解）上有一个算法比较符合，那就是动态规划中的“背包问题”。

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

如何选择最合适的物品放置于给定背包中，与我们的题目相符合，所以这次我们使用的是“0-1背包问题”，用我们这次的题目进行代入，“总人数” 等价于 “背包”，“物品” 等价于 “工单类型”，物品的重量就是所需人数。

补充：

背包问题解法延伸问题有三个：无界背包问题、0-1背包问题、二次背包问题 （不做详细延伸，只需我们使用的）

算法题目如下

所以最优解的答案是：决策n中五个技师中对应的值，1799元

PostMan提交参数：

people:5
carDetail[0][technician]:2
carDetail[0][amount]:49
carDetail[0][type]:全车安检
carDetail[1][technician]:2
carDetail[1][amount]:499
carDetail[1][type]:深度诊断
carDetail[2][technician]:3
carDetail[2][amount]:1300
carDetail[2][type]:二手车检测
carDetail[3][technician]:1
carDetail[3][amount]:10
carDetail[3][type]:空调专项检测

解答方式一：动态规划

 $i)
                {
                    $cacheMap[$j][$i] = $prevGain;
                    $cacheMapName[$j][$i] = $prevName;
                }
                else
                {
                    // 剩余价值
                    if ($i-$requiredPeople >= 0) {
                        $surplusPeople = $i-$requiredPeople;
                        $surplusGain = $cacheMap[$preLine][$surplusPeople];
                        $surplusName = $cacheMapName[$preLine][$surplusPeople];
                    }else {
                        $surplusGain = 0;
                        $surplusName = '';
                    }
                    $nowTotalGain = $gain + $surplusGain;
                    $cacheMap[$j][$i] = max($prevGain, $nowTotalGain);
                    if ($prevGain > $nowTotalGain) {
                        $cacheMapName[$j][$i] = $prevName;
                    }else{
                        $cacheMapName[$j][$i] = $name.'+'.$surplusName;
                    }
                }
            }
        }
        $actual = count($postData['carDetail']);
        return [
            'maxMatch' => $cacheMap[$actual][$totalPeople],
            'maxMatchName' => trim($cacheMapName[$actual][$totalPeople],'+')
        ];
    }
}
$bestMatch = new bestMatch;
if (empty($_POST) || isset($_POST['people']) && $_POST['people'] > 0) {
    die('提交参数有误');
}
$res = $bestMatch->getMethod($_POST);
$t2 = microtime(true);
echo '动态规划: '.'
';
echo '最佳金额: '.$res['maxMatch'].'
';
echo '最佳套餐搭配: '.$res['maxMatchName'].'
';
echo '耗时'.round($t2-$t1,7).'秒'.'
' ;
echo '消耗内存: ' . memory_get_usage().'字节'.'
' ;

解答方式二：递归

 0 ){
                $value['name'] = $up['name'].'+'.$array[$i]['type'];
                $value['amount'] = bcadd($up['amount'],$array[$i]['amount']);
                $value['technician'] = bcadd($up['technician'],$array[$i]['technician']);
            }else{
                $value['name'] = $array[$i]['type'];
                $value['amount'] = bcadd($array[$i]['amount'],0);
                $value['technician'] = bcadd($array[$i]['technician'],0);
            }
            $result[]  = $value;
            $this->getSortList($array,$i+1,$value,$result);
        }
        return $result ;
    }
    public function getMethod($postData)
    {
        $people = $postData['people'];
        $carDetail = $postData['carDetail'];
        $allResult = $this->getSortList($carDetail);
        $bestMatch = [];
        foreach ($allResult as $val) {
            if ($val['technician'] <= $people) {
                if ($bestMatch) {
                    if ($val['amount'] > $bestMatch['amount']) {
                        $bestMatch = $val;
                    }
                }else{
                    $bestMatch = $val;
                }
            }
        }
        return $bestMatch;
    }
}
$optimal = new optimal();
if (empty($_POST) || isset($_POST['people']) && $_POST['people'] > 0) {
    die('提交参数有误');
}
$bestMatch = $optimal->getMethod($_POST);
$t2 = microtime(true);
echo '递归查询: '.'
';
echo '最佳金额: '.$bestMatch['amount'].'
';
echo '最佳套餐搭配: '.$bestMatch['name'].'
';
echo '耗时'.round($t2-$t1,7).'秒'.'
' ;
echo '消耗内存: ' . memory_get_usage().'字节'.'
' ;

以上就是PHP实现动态规划之背包问题的详细内容，更多请关注 第一PHP社区 其它相关文章！