当前位置:Gxlcms > PHP教程 > php实现称砝码的方法介绍

php实现称砝码的方法介绍

时间:2021-07-01 10:21:17 帮助过:39人阅读

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

输入

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实现AOP的基础

php生成短连接的方法

以上就是php实现称砝码的方法介绍的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行