この記事では、0-1 ナップザック問題を解決するための PHP 動的プログラミングの例を分析します。皆さんの参考に共有してください。具体的な分析は次のとおりです:
ナップサックの問題の説明: 最大重量 W のバックパックには n 個のアイテムがあり、各アイテムの重量は t、各アイテムの値は v です。
このバックパックの重量を最大にする (ただし W を超えない) には、バックパックの値が最大である必要があります。
アイデア: 2 次元配列を定義します。1 つの次元は項目の数 (各項目を表す)、2 番目の次元は重み (最大値を超えない、ここでは 15) です。次の配列 a、
動的計画法の原理的な考え方、max(opt(i-1,w),wi+opt(i-1,w-wi))のうちの最大値
opt(i-1,w-wi) は前の最適解を参照します
?
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
//これは動的計画法の原理に基づいて書いたものです // max(opt(i-1,w),wi+opt(i-1,w-wi)) //バックパックは最大重量に耐えることができます $w=15; //4つのアイテムと各アイテムの重量は次のとおりです $dx=配列(3,4,5,6); //各アイテムの価値 $qz=配列(8,7,4,9); //配列を定義する $a=配列(); //初期化 for($i=0;$ifor ($j=0;$j//opt(i-1,w),wi+opt(i-1,w-wi) for ($j=1;$j for($i=1;$i $a[$j][$i]=$a[$j-1][$i]; //最大値 w=15 を超えない if($dx[$j-1]<=$w){ if(!isset($a[$j-1][$i-$dx[$j-1]])) 続行; //wi+opt(i-1,wi) $tmp = $a[$j-1][$i-$dx[$j-1]]+$qz[$j-1]; //opt(i-1,w),wi+opt(i-1,w-wi) => 比較 if($tmp>$a[$j][$i]){ $a[$j][$i]=$tmp; } } } } //この配列を出力し、最も高い値を持つ右端の値を出力します for ($j=0;$j for ($i=0;$i echo $a[$j][$i]."/t"; } echo "/n"; } ?>
|
http://www.bkjia.com/PHPjc/973132.html