刷表啊,用空间换时间
把表画出来会做得更快
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中文网!
相关推荐:
Atas ialah kandungan terperinci php实现称砝码的方法介绍. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!