求助Python3金明的预算方案
"""
每一个主件是一个组, 每一个附件是当前组的不同物品
状态表示:
f[i][j]:只从前i组物品中选,总价值不超过j的所有选法
属性:最大值
状态计算:
不选第i组物品:f[i][j] = f[i - 1][j]
选第i组物品:分为4中情况,因为附件最多2个。因此要么不选,要么选1号,要么选2号,要么1号2号都选
f[i][j] = f[i - 1][j - mv[i] - v[i][k]] + mw[i] + w[i][k]
f[0][0] = 0
"""
m, n = map(int, input().strip().split())
w = [[0] for _ in range(n + 1)]
v = [[0] for _ in range(n + 1)]
mw = [0]
mv = [0]
for i in range(1, n + 1):
a, p, q = map(int, input().strip().split())
if q == 0:
mv.append(a) # 对于当前主件体积为a
mw.append(p * a) # 价值=重要程度p*价格a
else:
# 如果为附件
v[q].append(a)
w[q].append(p * a)
# 预处理出附件的最后一种情况
for i in range(1, len(mv)):
if len(v[i]) == 3:
# print(v[i][1], v[i][2])
# print(w[i][1], w[i][2])
# print("------------")
v[i].append(v[i][1] + v[i][2])
w[i].append(w[i][1] + w[i][2])
# print(v[i][3], w[i][3])
# print("===========")
# print(w)
# print(v)
# print(mv)
# print(mw)
f = [[0] * (m + 20) for _ in range(n + 1)]
for i in range(1, len(mv)): # 第一维是遍历主件
# print(len(v[i]), v[1][2])
for j in range(0, m + 1):
# print(j)
f[i][j] = f[i - 1][j]
for k in range(0, len(v[i])):
if j >= mv[i] + v[i][k]:
f[i][j] = max(f[i][j], f[i - 1][j - mv[i] - v[i][k]] + mw[i] + w[i][k])
# print(f[i][j])
print(f[len(mv) - 1][m])