TA的其他文章
| python-贪吃的大嘴 浏览：354 |
| python-连接乘积 浏览：100 |
| python-选择排序 浏览：125 |
你可能喜欢
C语言程序设计教程（第三版）课后习题8.6 （C语言代码）浏览：1680 |
校门外的树 （C++代码）浏览：1013 |
C二级辅导-温度转换 （C语言代码）浏览：646 |
计算质因子 （C++代码）100以内质数直接打表就好了浏览：1322 |
C语言程序设计教程（第三版）课后习题1.6 （C语言代码）浏览：725 |
解题思路:
动态规划。
假设法码个数为n，所能称的最大重量为w，建立一个大小为（n+1）*(w+1)的二维数组。初始化的值都为零。
dp[i][j],代表当有i个法码时是否能称出重量为j的物品，如果能，则令dp[i][j] = 1。
状态转移方程：
if dp[i-1][j]:
dp[i][j] = 1 #第i个法码不放
dp[i][j+m[i]] = 1 #第i个法码放在法码盘
if j > m[i]:
dp[i][j-m[i]] #第i个法码放在物品盘
最后计算sum（dp[n]）即可。
注意事项:
参考代码:
n = int(input()) A = [int(i) for i in input().strip().split()] A.sort(reverse = True) A = [0] + A maxweight = sum(A) dp = [[0 for j in range(maxweight+1)] for i in range(n+1)] for i in range(n+1): dp[i][0] = 1 for i in range(1,n+1): for j in range(maxweight+1): if dp[i-1][j]: dp[i][j] = 1 dp[i][j+A[i]] = 1 if j > A[i]: dp[i][j-A[i]] = 1 print(sum(dp[n])-1)
0.0分
12 人评分
精彩推荐
printf基础练习2 （C语言代码）浏览：3404 |
C语言程序设计教程（第三版）课后习题1.5 （C语言代码）浏览：590 |
C语言程序设计教程（第三版）课后习题8.6 （C语言代码）浏览：609 |
不容易系列 （C语言代码）浏览：702 |
Pascal三角 （C语言代码）格式错误浏览：551 |
数组输出 （C语言代码）--此题的题目描述有问题浏览：1844 |
C语言程序设计教程（第三版）课后习题7.1 （C语言代码）浏览：539 |
C语言程序设计教程（第三版）课后习题5.7 （C语言代码）浏览：606 |
IP判断 （C语言代码）浏览：819 |
C语言程序设计教程（第三版）课后习题9.8 （C语言代码）浏览：646 |
D 2022-02-13 13:29:18 |
如果不排序的话可能会缺少讨论情况。 举个例子，假如说有三颗法码，重量分别为2，3，5 未经过排序时，当有两颗砝码时，你只能称出2种重量分别是，dp[2][2]，dp[2][5] 排序后，重量分别为5，3，2。当有两颗砝码时，你能称出3种重量分别是，dp[2][5]，dp[2][8]，和dp[2][2] 两者对比就会发现，未经过排序可能会缺少讨论情况。
D 2022-02-13 13:32:35 |
未排序时，当有两颗砝码时，其实实际中我们也能称出dp[2][1]，但是，如果不经过排序我们就得不到dp[2][1]。