php实现称砝码的方法介绍
php实现称砝码的方法介绍
内容导读
收集整理的这篇技术教程文章主要介绍了php实现称砝码的方法介绍，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2565字，纯文字阅读大概需要4分钟。
内容图文
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
输出
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网其它相关文章！
内容总结
以上是为您收集整理的php实现称砝码的方法介绍全部内容，希望文章能够帮你解决php实现称砝码的方法介绍所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
