刷表啊，用空間換時間
把表畫出來會做得更快
13 //动态规划就是一个表 14 //至于这个表的更新就是上面层的表更新下面层的，是逐级更新还是跳级更新要注意 15 //把表画出来做的更快
其實可以最開始想到的就是用所求做狀態
4 //dp就是思考变量（然后变量组合成初始状态）：变量有用几种砝码，每种砝码有多少个，重量为多少
用不同的初始狀態去試
一維不行就加到二維，二維不行就加到3維
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
2 1 2 2 1
5
1 <?php
2 //php本身是桶，所以这里用重量来做dp是可以的
3 //初始状态 最终状态 状态转移方程
4 //dp就是思考变量（然后变量组合成初始状态）：变量有用几种砝码，每种砝码有多少个，重量为多少
5 //f[i][j]表示用了第i种砝码用了j个所能达到的重量
6 //dp方程为：f[i+1][]=f[i][j]+
7
8 //f[i][j]表示前i种物品能否达到j重量
9 //f[i][j]=（或者关系）第i件物品取0到n(i)件能够达到
10 //f[i-1][j]||(取)f[i-1][j]+k*wi[k 0->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 ?>以上就是本文的全部內容，希望對大家的學習有所幫助，更多相關內容請關注PHP中文網！
相關建議：
以上是php實作稱砝碼的方法介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！
