// 動态規劃
error_reporting(E_ALL ^ E_NOTICE);
$t1= microtime(true);
classbestMatch
{
publicfunctiongetMethod($postData)
{
$peopleArr= $gainArr= $nameArr= [0];
foreach($postData['carDetail'] as$val) {
// 初始化各個套餐：所需人數、利潤和套餐名稱數組
$peopleArr[] = $val['technician'];
$gainArr[] = $val['amount'];
$nameArr[] = $val['type'];
}
// 擷取人數總數(背包)
$totalPeople= $postData['people'];
// 做檢測單數
$items= count($peopleArr);
// 利潤清單 - 初始狀态
$cacheMap[] = array_fill(1, $items, 0);
// 套餐清單 - 初始狀态
$cacheMapName[] = array_fill(1, $items, '');
//中間的各種決策(依次放入物品a,b,c,d,e)
// 第一個循環是總人數
for($i= 1; $i<= $totalPeople; $i++)
{
// 第二個循環是套餐
for($j= 1; $j< $items; $j++)
{
$requiredPeople= $peopleArr[$j];
$gain= $gainArr[$j];
$name= $nameArr[$j];
// 上一行坐标數
$preLine= $j-1;
$prevGain= $cacheMap[$preLine][$i];
$prevName= $cacheMapName[$preLine][$i];
if($requiredPeople> $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= newbestMatch;
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().'位元組'.'
';