01背包问题
分为二维解法和一维解法,一维解法空间内存占用少
二维解法
代码如下：
n, v = map(int, input().split())
goods = []
for i in range(n):
goods.append([int(i) for i in input().split()])
# 初始化，先全部赋值为0，这样至少体积为0或者不选任何物品的时候是满足要求
dp = [[0 for i in range(v+1)] for j in range(n+1)]
# i为商品号，表示第几个商品，j为体积，表示目前总体积
for i in range(1, n+1):
for j in range(1,v+1):
dp[i][j] = dp[i-1][j] # 第i个物品不选
if j>=goods[i-1][0]:# 判断背包容量是不是大于第i件物品的体积
# 在选和不选的情况中选出最大值
dp[i][j] = max(dp[i][j], dp[i-1][j-goods[i-1][0]]+goods[i-1][1])
#dp[-1][-1]即价值最大
print(dp[-1][-1])
里面的值的意思是，例：i = 3时，j = 4时，坐标即表示前三个物品在体积为4时的最大价值
上图是关于01背包二维解法中数组的表示，这是目前找到最清晰的关于数组的理解
一维解法
n, v = map(int, input().split())
goods = []
for i in range(n):
goods.append([int(i) for i in input().split()])
dp = [0 for i in range(v+1)]
for i in range(n):
for j in range(v,-1,-1):
if j >= goods[i][0]:
dp[j] = max(dp[j], dp[j-goods[i][0]] + goods[i][1])
print(dp[-1])