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
?
3 4 513 14
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 for ($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]; //Not greater than the maximum w=15 if($dx[$j-1] 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 for ($i=0;$i echo $a[$j][$i]."/t"; } echo "/n"; } ?> |
