php实现称砝码（背包）

一、总结

一句话总结：

1、dp的实质是什么？

刷表啊，用空间换时间

把表画出来会做得更快

13 //动态规划就是一个表14 //至于这个表的更新就是上面层的表更新下面层的，是逐级更新还是跳级更新要注意15 //把表画出来做的更快

2、dp的初始状态怎么得到（其实可以最开始想到的就是用所求做状态）？

其实可以最开始想到的就是用所求做状态

4 //dp就是思考变量（然后变量组合成初始状态）：变量有用几种砝码，每种砝码有多少个，重量为多少

3、dp的状态转移方程怎么得到？

用不同的初始状态去试

一维不行就加到二维，二维不行就加到3维

4、这里又忘记初始化中间数组了（在不同的组数据之间）？

26     $dp=null;27     $dp[0]=1;

二、称砝码（背包）

题目描述

现有一组砝码，重量互不相等，分别为m1,m2,m3…mn；

每种砝码对应的数量为x1,x2,x3...xn。现在要用这些砝码去称物体的重量，问能称出多少中不同的重量。

注：

称重重量包括0

方法原型：public static int fama(int n, int[] weight, int[] nums)

输入描述:

输入包含多组测试数据。 对于每组测试数据： 第一行：n --- 砝码数(范围[1,10]) 第二行：m1 m2 m3 ... mn --- 每个砝码的重量(范围[1,2000]) 第三行：x1 x2 x3 .... xn --- 每个砝码的数量(范围[1,6])

输出描述:

利用给定的砝码可以称出的不同的重量数

示例1

输入

21 22 1

输出

代码：

1 
     ni]11 //f[i][j][k]表示前i种物品取j件能否达到k重量12 13 //动态规划就是一个表14 //至于这个表的更新就是上面层的表更新下面层的，是逐级更新还是跳级更新要注意15 //把表画出来做的更快16 while($n=trim(fgets(STDIN))){17     $w=trim(fgets(STDIN));18     $num=trim(fgets(STDIN));19     $w=explode(' ',$w);20     $num=explode(' ',$num);21     $total=10;22     for($i=0;$i<$n;$i++){23         $total+=$w[$i]*$num[$i];24     }25 26     $dp=null;27     $dp[0]=1;28     for($i=1;$i<=$n;$i++){29         for($j=$total;$j>=0;$j--){30             for($k=0;$k<=$num[$i-1];$k++){31                 if($j-$k*$w[$i-1]>=0&&$dp[$j-$k*$w[$i-1]]){32                     $dp[$j]=1;33                     break;34                 } 35             }36         }37     }38     echo count($dp).PHP_EOL;39     //print_r($w);40     //print_r($num);41 42 }43 ?>