この記事の例では、PHP 貪欲アルゴリズムを使用して 0-1 ナップザック問題を解く方法を説明します。参考のためにみんなで共有してください。具体的な分析は次のとおりです:
貪欲アルゴリズムは 0-1 ナップザック問題を解決し、局所最適解を通じて大域最適解が得られます。動的プログラミングよりも柔軟にナップサック問題を解決しましょう!
?
|
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
//0-1 バックパック貪欲アルゴリズム問題 クラスタンキシン{ 公開 $weight; 公開価格; パブリック関数 __construct($weight=0,$price=0) { $this->weight=$weight; $this->価格=$価格; } } //データを生成する $n=10; for($i=1;$i $weight=ランド(1,20); $price=ランド(1,10); $x[$i]=新しいタンキシン($重量,$価格); } //結果を出力する 機能表示($x) { $len=カウント($x); foreach($x を $val){ echo $val->weight,' ',$val->price; エコー ' } } //価格と重量比で並べ替えます 関数 tsort(&$x) { $len=カウント($x); for($i=1;$i { for($j=1;$j { $temp=$x[$j]; $res=$x[$j+1]->価格/$x[$j+1]->重量; $temres=$temp->価格/$temp->重量; if($res>$temres){ $x[$j]=$x[$j+1]; $x[$j+1]=$temp; } } } } //貪欲なアルゴリズム 関数タンキシン($x,$totalweight=50) { $len=カウント($x); $allprice=0; for($i=1;$i if($x[$i]->weight>$totalweight) ブレーク; その他{ $allprice+=$x[$i]->価格; $総重量=$総重量-$x[$i]->重量; } } if($iprice*($totalweight/$x[$i]->weight); $allprice を返す; } tsort($x);//非昇順に並べ替えます display($x);//ディスプレイ echo '0-1 バックパックの最適解は次のとおりです:'; エコータンシン($x); |
この記事で説明した内容が皆様の PHP プログラミング設計に役立つことを願っています。