解题思路:
一维费用背包问题(多重背包)
注意事项:
参考代码:
from cmath import inf def f(n,m): dp = [inf for j in range(m+1)] dp[0] = 0 V = [None] W = [None] for i in range(1,n+1): v,num = map(int,input().strip().split()) k = 1 while num >= k: num = num - k W.append(k) V.append(k*v) k = k*2 if num > 0: W.append(num) V.append(num*v) for i in range(1,len(W)): for j in range(m,V[i]-1,-1): dp[j] = min(dp[j],dp[j-V[i]]+W[i]) if dp[m] != inf: print(dp[m]) else: print('><') if __name__ == '__main__': m,n = map(int,input().strip().split()) f(n,m)
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题1.5 (C++代码)浏览:1094 |
三角形 (C++代码)记忆化搜索浏览:1234 |
剪刀石头布 (C语言代码)浏览:752 |
【计算两点间的距离】 (C语言代码)浏览:1493 |
关于C语言变量位置的问题浏览:272 |
星期判断机 (C语言代码)浏览:859 |
矩形面积交 (C++代码)浏览:1129 |
1035 题解浏览:785 |
川哥的吩咐 (C语言代码)浏览:611 |
C二级辅导-统计字符 (C语言代码)浏览:647 |