1. 首页
  2. 题解列表
  3. 2604题题解

python-砝码称重

1377 阅读 3 评论
原题链接：蓝桥杯2021年第十二届省赛真题-砝码称重

解题思路:

参考博客https://blog.csdn.net/qq_52441682/article/details/122634449?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&utm_relevant_index=2


动态规划。

假设法码个数为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.0分

8 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
点进来你会后悔的
点进来你会后悔的
简简单单的循环
简简单单的循环
简单的回文数
简单的回文数

评论列表 共有 3 条评论

D 2年前 回复TA 
@whoami 未排序时，当有两颗砝码时，其实实际中我们也能称出dp[2][1]，但是，如果不经过排序我们就得不到dp[2][1]。
D 2年前 回复TA 
@whoami 如果不排序的话可能会缺少讨论情况。 举个例子，假如说有三颗法码，重量分别为2，3，5 未经过排序时，当有两颗砝码时，你只能称出2种重量分别是，dp[2][2]，dp[2][5] 排序后，重量分别为5，3，2。当有两颗砝码时，你能称出3种重量分别是，dp[2][5]，dp[2][8]，和dp[2][2] 两者对比就会发现，未经过排序可能会缺少讨论情况。
whoami 2年前 回复TA 
厉害，大佬。请问为什么A[]中的值，也就是砝码重量，必须要顺序从大到小？
我尝试从小到大结果就会错误

是因为从小到大的话，在后面大砝码的循环中，不会进入17行的判断中去了吗？