0-1 ナップザック問題を解決するための PHP 貪欲アルゴリズムの分析例

0-1 ナップザック問題を解決するための PHP 貪欲アルゴリズムの分析例_PHP チュートリアル

WBOY

リリース： 2016-07-13 10:00:41

オリジナル

1022 人が閲覧しました

PHP貪欲アルゴリズムは0-1ナップザック問題を解決する例の分析

この記事では主に0-1ナップサック問題を解決するためのPHP貪欲アルゴリズムを紹介し、例では貪欲アルゴリズムの原理とナップザックの実装スキルを分析します。問題がありますので、必要な友達は参考にしてください

この記事の例では、PHP 貪欲アルゴリズムを使用して 0-1 ナップザック問題を解く方法を説明します。参考のためにみんなで共有してください。具体的な分析は次のとおりです:

貪欲アルゴリズムは 0-1 ナップザック問題を解決し、局所最適解を通じて大域最適解が得られます。動的プログラミングよりも柔軟にナップサック問題を解決しましょう!

//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 プログラミング設計に役立つことを願っています。