PHP は動的プログラミングのナップザック問題を実装します

事件の原因

弊社でアルゴリズムプログラミングコンテストを開催したため、下図のアルゴリズム問題がランダムに抽選されたのですが、しばらく考えて思い出したのです。この本には 1 つありました (アルゴリズムの図解) このアルゴリズムは、動的計画法における「ナップザック問題」とより一致しています。

ナップザック問題は、組み合わせ最適化の NP 完全問題です。この問題は、次のように説明できます。アイテムのセットが与えられ、各アイテムには独自の重量と価格があり、制限された合計重量の範囲内で、アイテムの合計価格が最高になるように選択するにはどうすればよいですか。

特定のバックパックに入れる最適なアイテムを選択する方法は私たちの質問と一致しているため、今回は「0-1 バックパック問題」を使用し、それを今回の質問で置き換えます。 「人数」は「バックパック」、「アイテム」は「作業指示書の種類」に相当し、アイテムの重量が必要人数となります。

補足:

ナップサック問題の解法の拡張問題には、無制限ナップサック問題、0-1 ナップサック問題、二次ナップサック問題の 3 つがあります (詳細な拡張はありません)。

アルゴリズムのトピックは次のとおりです。

動的計画法で扱われる問題は、多段階の意思決定です。 - 問題作成。通常は初期状態から開始します。状態が開始され、中間段階での決定の選択を通じて最終状態に到達します。これらの決定は決定シーケンスを形成し、プロセス全体を完了するためのアクティビティ ルート (通常は最適なアクティビティ ルート) を決定します。動的プログラミングの設計には特定のパターンがあり、通常は次のステップが含まれます。

初期状態→│意思決定 1│→│意思決定 2│→...→│意思決定ｎ│→終了状​​態

動的計画法の問題解決公式:

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

# 横 m (人数の合計)、縦 n (車両 4 台による作業指示の種類)

● f(n-1,m) == > (決定 1) 前の作業指示タイプに対応する技術者の数、および作業指示の利益

#● P(n,m) ==> (決定 2) 技術者の数現在の作業指示書のタイプと完了した作業に対応する 単一の利益

# f(n-1,m-w[n]) ==> 現在の作業指示書に必要な人数を引くことにより、前回の決定で対応する人数の利益

したがって、最適解の答えは次のようになります。決定 n での 5 人の技術者の対応する値、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]:空调专项检测

解決策 1: 動的プログラミング

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

解決策 2: 再帰

りー

以上がPHP は動的プログラミングのナップザック問題を実装しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。