[php]0-1背包动态规划

时间：2011-03-11 来源：一缕青烟

0-1背包是经典问题，有必要常常复习。

已知3件重量物品重量为3,4,5.价格分别为4,5,6

现背包负重极限为9，在背包内物品不限定个数的情况下，使背包内放置的物品价格最大化。

 1 <?php
 2  $weight     = array(3,4,5);
 3  $price      = array(4,5,6);
 4  $limitw     = 9;
 5  $ps = array();
 6 for($i = 1 ; $i <= $limitw ; $i++) :
 7     foreach( $weight as $k=>$v) :
 8         $o = $i -$v;
 9         $l = $weight[$k-1];
10         //假设同一个物品有N件,可以重复放置 
11         $lp = max($ps[$o][$l],$ps[$o][$v]);
12         //假设同一个物品只能放入背包一次
13         //$lp = $ps[$o][$l];
14         if( $v <= $i) :
15                 if( $price[$k] + $lp > $ps[$i][$l]) :
16                         $ps[$i][$v] = $price[$k]  + $lp;
17                 else :
18                     $ps[$i][$v] = $ps[$i][$l];
19                 endif;
20         else :
21             $ps[$i][$v] = $ps[$i][$l];
22         endif;
23     endforeach;
24 endfor;
25 echo "<pre/>";
26 print_r( $ps );//echo end(end($ps))即为最优解
27 ?>