TA的其他文章
| python-数字三角形 浏览：374 |
| python-平面切分 浏览：392 |
| python-蓝肽子序列 浏览：518 |
你可能喜欢
解题思路:
动态规划。
假设法码个数为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 人评分
精彩推荐
C语言程序设计教程（第三版）课后习题12.5 （C语言代码）浏览：830 |
C语言考试练习题_排列 （C++代码）浏览：639 |
C语言程序设计教程（第三版）课后习题6.4 （C语言代码）浏览：597 |
C语言程序设计教程（第三版）课后习题1.5 （C语言代码）浏览：589 |
2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）浏览：632 |
c primer plus 第十二章 12.1小节浏览：377 |
不会做的浏览：874 |
剪刀石头布 （C语言代码）浏览：752 |
C语言程序设计教程（第三版）课后习题6.2 （C语言代码）浏览：690 |
printf基础练习2 （C语言代码）浏览：747 |
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]。