PHP implementiert das Rucksackproblem der dynamischen Programmierung

Der Grund für den Vorfall

Da unser Unternehmen einen Algorithmus-Programmierwettbewerb veranstaltete und die Algorithmusfragen im Bild unten zufällig auswählte, dachte ich eine Weile darüber nach und erinnerte mich daran war einer in dem Buch (Algorithmusillustration). Der Algorithmus stimmt eher mit dem „Rucksackproblem“ in der dynamischen Programmierung überein.

Das Knapsack-Problem ist ein NP-vollständiges Problem der kombinatorischen Optimierung. Das Problem kann wie folgt beschrieben werden: Bei einer gegebenen Menge von Artikeln hat jeder Artikel sein eigenes Gewicht und seinen eigenen Preis. Wie wählen wir innerhalb des begrenzten Gesamtgewichts aus, damit der Gesamtpreis der Artikel am höchsten ist?

Wie man die am besten geeigneten Gegenstände für einen bestimmten Rucksack auswählt, stimmt mit unserer Frage überein. Daher verwenden wir dieses Mal das „0-1-Rucksackproblem“ und ersetzen es diesmal durch unsere Frage „Gesamt“. „Anzahl der Personen“ entspricht „Rucksack“, „Artikel“ entspricht „Arbeitsauftragsart“ und das Gewicht des Artikels entspricht der Anzahl der benötigten Personen.

Ergänzung:

Es gibt drei Erweiterungsprobleme der Rucksackproblemlösung: unbegrenztes Rucksackproblem, 0-1 Rucksackproblem und quadratisches Rucksackproblem (ohne detaillierte Erweiterung, nur Wir verwenden)

Das Algorithmusthema ist wie folgt

Das Problem der dynamischen Programmierung ist eine mehrstufige Entscheidung -Erstellungsproblem, im Allgemeinen ausgehend vom Anfangszustand Der Zustand beginnt und erreicht den Endzustand durch die Auswahl von Entscheidungen in den Zwischenstadien. Diese Entscheidungen bilden eine Entscheidungssequenz und bestimmen eine Aktivitätsroute zum Abschluss des gesamten Prozesses (normalerweise die optimale Aktivitätsroute). Der Entwurf der dynamischen Programmierung weist ein bestimmtes Muster auf, das im Allgemeinen die folgenden Schritte umfasst.

Anfangszustand→│Entscheidung 1│→│Entscheidung 2│→…→│Entscheidungｎ│→Endzustand

Problemlösungsformel für dynamische Programmierung:

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

● Horizontal m (Gesamtzahl der Personen), vertikal n (Art des von 4 Fahrzeugen ausgeführten Arbeitsauftrags)

● f(n-1,m) ==> (Entscheidung 1) Die Anzahl der Techniker, die dem vorherigen Arbeitsauftragstyp entsprechen, und der Gewinn des Arbeitsauftrags

● P(n,m) ==> (Entscheidung 2) Die Anzahl der Techniker, die dem entsprechen aktueller Arbeitsauftragstyp und die geleistete Arbeit Einzelgewinn

● f(n-1,m-w[n]) ==> Subtrahieren Sie die Anzahl der für den aktuellen Arbeitsauftrag erforderlichen Personen und den entsprechenden Gewinn die Anzahl der Personen in der vorherigen Entscheidung

Die Antwort auf die optimale Lösung lautet also: der entsprechende Wert unter den fünf Technikern in Entscheidung n, 1799 Yuan

PostMan-Übermittlungsparameter:

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]:空调专项检测

Lösungsmethode eins: dynamische Programmierung

<?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; ;

Lösungsmethode zwei: Rekursion

<?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; ;

Das obige ist der detaillierte Inhalt vonPHP implementiert das Rucksackproblem der dynamischen Programmierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!