PHP implémente un problème de sac à dos de programmation dynamique

La raison de l'incident

Parce que notre société a organisé un concours de programmation d'algorithmes et a sélectionné au hasard les questions d'algorithme dans l'image ci-dessous, j'y ai réfléchi pendant un moment et je me suis souvenu qu'il y avait en était un dans le livre (Algorithm Illustration). L'algorithme est plus cohérent avec le "problème du sac à dos" en programmation dynamique.

Le problème Knapsack est un problème NP-complet d'optimisation combinatoire. Le problème peut être décrit comme suit : étant donné un ensemble d'articles, chaque article a son propre poids et son propre prix, dans le cadre du poids total limité, comment choisissons-nous pour que le prix total des articles soit le plus élevé.

Comment choisir les articles les plus appropriés à placer dans un sac à dos donné est cohérent avec notre question, donc cette fois nous utilisons le « problème du sac à dos 0-1 » et utilisons cette fois notre question pour le remplacer. nombre de personnes » équivaut à « sac à dos », « article » équivaut à « type de bon de travail » et le poids de l'article correspond au nombre de personnes requises.

Supplément :

Il existe trois problèmes d'extension de la solution du problème du sac à dos : le problème du sac à dos illimité, le problème du sac à dos 0-1 et le problème du sac à dos quadratique (sans extension détaillée, juste que nous utilisons)

Le sujet de l'algorithme est le suivant

Le problème traité par la programmation dynamique est une décision en plusieurs étapes -faire un problème, généralement à partir de l'état initial. L'état commence et atteint l'état final grâce à la sélection de décisions dans les étapes intermédiaires. Ces décisions forment une séquence de décision et déterminent un itinéraire d'activité pour terminer l'ensemble du processus (généralement l'itinéraire d'activité optimal). La conception de la programmation dynamique suit un certain modèle, qui implique généralement les étapes suivantes.

État initial →│Décision 1│→│Décision 2│→…→│Décisionｎ│→État final

Formule de résolution de problèmes de programmation dynamique :

f(n,m)=max{f(n-1,m),f(n-1,m-w[n])+P(n,m)}

● Horizontal m (nombre total de personnes), vertical n (type de bon de travail effectué par 4 véhicules)

● f(n-1,m) ==> (Décision 1) Le nombre de techniciens correspondant au type de bon de travail précédent, et le bénéfice du bon de travail

● P(n,m) ==> (Décision 2) Le nombre de techniciens correspondant au type d'ordre de travail actuel et le travail effectué Bénéfice unique

● f(n-1,m-w[n]) ==> Soustraire le nombre de personnes requises pour l'ordre de travail en cours et le profit correspondant au nombre de personnes dans la décision précédente

Donc la réponse à la solution optimale est : la valeur correspondante parmi les cinq techniciens dans la décision n, 1799 yuans

Paramètres de soumission 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]:空调专项检测

Méthode de solution 1 : programmation dynamique

<?php
// 动态规划
error_reporting(E_ALL ^ E_NOTICE);
$t1 = microtime(true);
class bestMatch
{
    public function getMethod($postData)
    {
        $peopleArr = $gainArr = $nameArr = [0];
        foreach ($postData[&#39;carDetail&#39;] as $val) {
            // 初始化各个套餐：所需人数、利润和套餐名称数组
            $peopleArr[] = $val[&#39;technician&#39;];
            $gainArr[] = $val[&#39;amount&#39;];
            $nameArr[] = $val[&#39;type&#39;];
        }
        // 获取人数总数（背包）
        $totalPeople = $postData[&#39;people&#39;];
        // 做检测单数
        $items = count($peopleArr);
        // 利润列表 - 初始状态
        $cacheMap[] = array_fill(1, $items, 0);
        // 套餐列表 - 初始状态
        $cacheMapName[] = array_fill(1, $items, &#39;&#39;);
        //中间的各种决策(依次放入物品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 = &#39;&#39;;
                    }
                    $nowTotalGain = $gain + $surplusGain;
                    $cacheMap[$j][$i] = max($prevGain, $nowTotalGain);
                    if ($prevGain > $nowTotalGain) {
                        $cacheMapName[$j][$i] = $prevName;
                    }else{
                        $cacheMapName[$j][$i] = $name.&#39;+&#39;.$surplusName;
                    }
                }
            }
        }
        $actual = count($postData[&#39;carDetail&#39;]);
        return [
            &#39;maxMatch&#39; => $cacheMap[$actual][$totalPeople],
            &#39;maxMatchName&#39; => trim($cacheMapName[$actual][$totalPeople],&#39;+&#39;)
        ];
    }
}
$bestMatch = new bestMatch;
if (empty($_POST) || isset($_POST[&#39;people&#39;]) && $_POST[&#39;people&#39;] > 0) {
    die(&#39;提交参数有误&#39;);
}
$res = $bestMatch->getMethod($_POST);
$t2 = microtime(true);
echo &#39;动态规划: &#39;.&#39;<br/>&#39;;
echo &#39;最佳金额: &#39;.$res[&#39;maxMatch&#39;].&#39;<br/>&#39;;
echo &#39;最佳套餐搭配: &#39;.$res[&#39;maxMatchName&#39;].&#39;<br/>&#39;;
echo &#39;耗时&#39;.round($t2-$t1,7).&#39;秒&#39;.&#39;<br/>&#39; ;
echo &#39;消耗内存: &#39; . memory_get_usage().&#39;字节&#39;.&#39;<br/>&#39; ;

Méthode de solution deux : récursivité

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!