PHP greedy algorithm to solve the 0-1 knapsack problem example analysis_PHP tutorial

PHP greedy algorithm solves the 0-1 knapsack problem example analysis

This article mainly introduces the PHP greedy algorithm to solve the 0-1 knapsack problem, and analyzes the principles and principles of the greedy algorithm with examples. Friends who need the implementation skills of the knapsack problem can refer to it

The example in this article describes the method of PHP greedy algorithm to solve the 0-1 knapsack problem. Share it with everyone for your reference. The specific analysis is as follows:

The greedy algorithm solves the 0-1 knapsack problem, and the global optimal solution is obtained through the local optimal solution! More flexible than dynamic programming to solve the knapsack problem!

?

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背包贪心算法问题 class tanxin{ public $weight; public $price; public function __construct($weight=0,$price=0) { $this->weight=$weight; $this->price=$price; } } //生成数据 $n=10; for($i=1;$i<=$n;$i ){ $weight=rand(1,20); $price=rand(1,10); $x[$i]=new tanxin($weight,$price); } //输出结果 function display($x) { $len=count($x); foreach($x as $val){ echo $val->weight,' ',$val->price; echo ' '; } } //按照价格和重量比排序 function tsort(&$x) { $len=count($x); for($i=1;$i<=$len;$i ) { for($j=1;$j<=$len-$i;$j ) { $temp=$x[$j]; $res=$x[$j 1]->price/$x[$j 1]->weight; $temres=$temp->price/$temp->weight; if($res>$temres){ $x[$j]=$x[$j 1]; $x[$j 1]=$temp; } } } } //贪心算法 function tanxin($x,$totalweight=50) { $len=count($x); $allprice=0; for($i=1;$i<=$len;$i ){ if($x[$i]->weight>$totalweight) break; else{ $allprice =$x[$i]->price; $totalweight=$totalweight-$x[$i]->weight; } } if($i<$len) $allprice =$x[$i]->price*($totalweight/$x[$i]->weight); return $allprice; } tsort($x);//按非递增次序排序 display($x);//显示 echo '0-1背包最优解为:'; echo tanxin($x);

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 backpack greedy algorithm problem class tanxin{ public $weight; public $price; public function __construct($weight=0,$price=0) { $this->weight=$weight; $this->price=$price; } } //Generate data $n=10; for($i=1;$i<=$n;$i ){<🎜> <🎜>$weight=rand(1,20);<🎜> <🎜>$price=rand(1,10);<🎜> <🎜>$x[$i]=new tanxin($weight,$price);<🎜> <🎜>}<🎜> <🎜>//Output results<🎜> <🎜>function display($x)<🎜> <🎜>{<🎜> <🎜>$len=count($x);<🎜> <🎜>foreach($x as $val){<🎜> <🎜>echo $val->weight,' ',$val->price; echo '
'; } } //Sort by price and weight ratio function tsort(&$x) { $len=count($x); for($i=1;$i<=$len;$i )<🎜> <🎜>{<🎜> <🎜>for($j=1;$j<=$len-$i;$j )<🎜> <🎜>{<🎜> <🎜>$temp=$x[$j];<🎜> <🎜>$res=$x[$j 1]->price/$x[$j 1]->weight; $temres=$temp->price/$temp->weight; if($res>$temres){ $x[$j]=$x[$j 1]; $x[$j 1]=$temp; } } } } //Greedy algorithm function tanxin($x,$totalweight=50) { $len=count($x); $allprice=0; for($i=1;$i<=$len;$i ){<🎜> <🎜>if($x[$i]->weight>$totalweight) break; else{ $allprice =$x[$i]->price; $totalweight=$totalweight-$x[$i]->weight; } } if($i<$len) $allprice =$x[$i]->price*($totalweight/$x[$i]->weight); return $allprice; } tsort($x);//Sort in non-increasing order display($x);//Display echo 'The optimal solution for the 0-1 backpack is:'; echo tanxin($x);

I hope this article will be helpful to everyone’s PHP programming design.

http://www.bkjia.com/PHPjc/973134.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/973134.htmlTechArticlePHP greedy algorithm solves the 0-1 knapsack problem example analysis. This article mainly introduces the PHP greedy algorithm to solve the 0-1 problem. Knapsack problem, an example analysis of the principles of greedy algorithm and implementation techniques of knapsack problem, need...