Example Analysis of PHP Dynamic Programming to Solve 0-1 Knapsack Problem

Example Analysis of PHP Dynamic Programming to Solve 0-1 Knapsack Problem_PHP Tutorial

WBOY

Release： 2016-07-13 10:00:29

Original

1167 people have browsed it

An example analysis of PHP dynamic programming to solve the 0-1 knapsack problem

This article mainly introduces PHP dynamic programming to solve the 0-1 knapsack problem. An example analysis of the principles and principles of the knapsack problem For implementation tips, friends in need can refer to it

This article analyzes the example of PHP dynamic programming to solve the 0-1 knapsack problem. Share it with everyone for your reference. The specific analysis is as follows:

Knapsack problem description: A backpack with a maximum weight of W now has n items, each item has a weight of t, and the value of each item is v.
To make the weight of this backpack the largest (but not exceeding W), the value of the backpack needs to be the largest.

Idea: Define a two-dimensional array, one dimension is the number of items (representing each item), and the second dimension is the weight (not exceeding the maximum, here is 15), the following array a,
The principle idea of dynamic programming, the maximum value among max(opt(i-1,w),wi opt(i-1,w-wi)),
opt(i-1,w-wi) refers to the previous optimal solution

//这是我根据动态规划原理写的

// max(opt(i-1,w),wi opt(i-1,w-wi))

//背包可以装最大的重量

$w=15;

//这里有四件物品,每件物品的重量

$dx=array(3,4,5,6);

//每件物品的价值

$qz=array(8,7,4,9);

//定义一个数组

$a=array();

//初始化

for($i=0;$i<=15;$i ){ $a[0][$i]=0; }

for ($j=0;$j<=4;$j ){ $a[$j][0]=0; }

//opt(i-1,w),wi opt(i-1,w-wi)

for ($j=1;$j<=4;$j ){

for($i=1;$i<=15;$i ){

$a[$j][$i]=$a[$j-1][$i];

//不大于最大的w=15

if($dx[$j-1]<=$w){

if(!isset($a[$j-1][$i-$dx[$j-1]])) continue;

//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<=4;$j ){

for ($i=0;$i<=15;$i ){

echo $a[$j][$i]."/t";

} echo "/n";

}

1 2

4 5

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

<🎜>//This is what I wrote based on the principle of dynamic programming<🎜> <🎜>// max(opt(i-1,w),wi opt(i-1,w-wi))<🎜> <🎜>//The backpack can hold the maximum weight<🎜> <🎜>$w=15;<🎜> <🎜>//There are four items here, the weight of each item<🎜> <🎜>$dx=array(3,4,5,6);<🎜> <🎜>//The value of each item<🎜> <🎜>$qz=array(8,7,4,9);<🎜> <🎜>//Define an array<🎜> <🎜>$a=array();<🎜> <🎜>//Initialization<🎜> <🎜>for($i=0;$i<=15;$i ){ $a[0][$i]=0; }<🎜> <🎜>for ($j=0;$j<=4;$j ){ $a[$j][0]=0; }<🎜> <🎜>//opt(i-1,w),wi opt(i-1,w-wi)<🎜> <🎜>for ($j=1;$j<=4;$j ){<🎜> <🎜>for($i=1;$i<=15;$i ){<🎜> <🎜>$a[$j][$i]=$a[$j-1][$i];<🎜> <🎜>//Not greater than the maximum w=15<🎜> <🎜>if($dx[$j-1]<=$w){<🎜> <🎜>if(!isset($a[$j-1][$i-$dx[$j-1]])) continue;<🎜> <🎜>//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) => Compare <🎜> <🎜>if($tmp>$a[$j][$i]){ $a[$j][$i]=$tmp; } } } } //Print this array and output the value in the rightmost corner which is the maximum value for ($j=0;$j<=4;$j ){<🎜> <🎜>for ($i=0;$i<=15;$i ){<🎜> <🎜>echo $a[$j][$i]."/t";<🎜> <🎜>} echo "/n";<🎜> <🎜>}<🎜> <🎜>?>

I hope this article will be helpful to everyone’s PHP programming design. http://www.bkjia.com/PHPjc/973132.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/973132.htmlTechArticlePHP dynamic programming solves the 0-1 knapsack problem example analysis. This article mainly introduces PHP dynamic programming to solve the 0-1 problem. Knapsack problem, examples analyze the principles and implementation techniques of the knapsack problem. Friends who need it can...