题目描述
小明有一个容量为 V 的背包。
这天他去商场购物，商场一共有 N 件物品，第 i件物品的体积为 wi，价值为 vi。
小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 1行包含两个正整数N,V，表示商场物品的数量和小明的背包容量。
第 2∼N+1 行包含 2 个正整数 w,v，表示物品的体积和价值。
1≤N≤10^2，1≤V≤10^3，1≤wi,vi≤10^3。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
1. 5 20 2. 1 6 3. 2 5 4. 3 8 5. 5 15 6. 3 3
输出
37
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
思路
设计DP状态：
定义二维数组dp[][],大小为N*C，dp[i][j]表示把前i个物品装入容量为j的背包中获得的最大值。我们把每个dp[i][j]都看成一个背包，背包的容量是j，装1~i这些物品。最后得到的dp[N][C]就是问题的答案。
状态转移方程：
我们考虑两种情况，如果i个物体比容积j大，则说明他肯定装不下，直接继承前i-1个物品装进容积j的背包情况即可。
dp[i][j] = dp[i-1][j]
如果第i个物品比j小，能进背包。此时分为两种情况
1.装第i个。从前i-1个物品的情况推广而来，前i-1个物品时dp[i-1][j]、第i个物品装进背包后，背包容积减少c[i]，价值增加w[i]
dp[i][j] = dp[i-1][j-c[i]] + w[i]
2.不装第i个，那么
dp[i][j] = dp[i-1][j]
我们取两种状态的最大值，得到状态转移方程
dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+w[i])
代码
1. N=3011 2. dp = [[0 for i in range(N)] for j in range(N)] 3. w = [0 for i in range(N)] 4. c = [0 for i in range(N)] 5. 6. def solve(n,C): 7. for i in range(1,n+1): 8. for j in range (0,C+1): 9. if c[i]>j : 10. dp[i][j] = dp[i-1][j] 11. else : 12. dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+w[i]) 13. return dp[n][C] 14. 15. n, C = map(int, input().split()) 16. for i in range(1, n+1): 17. c[i], w[i] = map(int, input().split()) 18. print(solve(n, C))
优化代码
1. N=3011 2. dp=[[0 for i in range(N)] for j in range(2)] 3. w=[0 for i in range(N)] 4. c=[0 for i in range(N)] 5. 6. def solve(n,C): 7. #由于当前状态只与前一个状态有关 8. #故设计滚动数组优化空间复杂度 9. now = 0 10. old =1 11. for i in range(1,n+1): 12. old,now = now,old #交换 13. for j in range (0,C+1): 14. if c[i] > j: 15. dp[now][j]=dp[old][j] 16. else: 17. dp[now][j] = max(dp[old][j], dp[old][j-c[i]]+w[i]) 18. return dp[now][C] 19. 20. n,C=map(int,input().split()) 21. for i in range(1,n+1): 22. c[i],w[i]=map(int,input().split()) 23. 24. print(solve(n,C))
