解题思路:
一维费用背包问题(多重背包)
注意事项:
参考代码:
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语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:436 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:771 |
简单的a+b (C语言代码)浏览:340 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:611 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:373 |
蓝桥杯历届试题-翻硬币 (C++代码)浏览:892 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:492 |
简单的a+b (C语言代码)浏览:504 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:1005 |
C语言训练-斐波纳契数列 (C语言代码)浏览:600 |