解题思路:
①建立一个存放物品的n*2大小的数组commodities[n+1][2],commodities[i][0]表示第i个物品的重量,commodities[i][1]表示第i个物品的价值。
②建立一个大小为m+1的数组dp[m+1],dp[i]表示背包剩余容量为m时,所能装载的最大价值。
③状态转移方程为dp[j] = max(dp[j],dp[j-commodities[i][0]]+commodities[i][1])
拿例题来进行测试,每个表格中的数据表示的是dp[i],即背包容量为i时的最大价值,每扫描一个商品都会对dp数组进行更新。
注意事项:
参考代码1:
def f(n,m): commodities = [[0 for j in range(2)] for i in range(n+1)] for i in range(1,n+1): commodities[i][0],commodities[i][1] = map(int,input().strip().split()) dp = [0 for i in range(m+1)] for i in range(1,n+1): #对每一个商品进行装载测试 for j in range(m,commodities[i][0]-1,-1): #这里j的范围为[m,commodities[i][0]],解决了背包剩下空间不够装该物品的情况 dp[j] = max(dp[j],dp[j-commodities[i][0]]+commodities[i][1]) print(dp[m]) if __name__ == '__main__': n,m = map(int,input().strip().split()) f(n,m)
参考代码2:
dp[i][j]表示有前i种物品,背包容量为j时所能装载的最大价值
def f(n,m): dp = [[0 for j in range(m+1)] for i in range(n+1)] w = [0 for i in range(n+1)] #存放物品重量 v = [0 for i in range(n+1)] #存放物品价值 for i in range(1,n+1): w[i],v[i] = map(int,input().strip().split()) for i in range(1,n+1): for j in range(m+1): if j < w[i]: #容量不够装第i种物品 dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]) #在装与不装第i种物品间选择价值最大的情况 print(dp[n][m]) if __name__ == '__main__': n,m = map(int,input().strip().split()) f(n,m)
0.0分
5 人评分
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:439 |
分糖果 (C++代码)浏览:1459 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:554 |
核桃的数量 (C语言代码)浏览:873 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:623 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:539 |
字符串比较 (C语言代码)浏览:703 |
简单的a+b (C语言代码)浏览:836 |
敲七 (C++代码)浏览:1062 |
简单的a+b (C语言代码)浏览:592 |