题目描述
在某网络游戏中提供了一个道具库,在道具库中每种道具均有若干件(数量已知),游戏玩家购买一件道具将获得一定的魅力值。
已知每种道具的价格和魅力值,请编写一个程序,在总价格不超过某个上限的情况下使得所购道具的魅力值之和达到最大。
输入
每组测试数据的输入有n+1行,n表示道具的种类。(n<=100,p<=10000)
第1行包含两个正整数,分别表示道具种类数n和总价值的上限p,两个数字之间用空格隔开。
第2行到第n+1行分别对应于第1种道具到第n种道具的信息,每1行包含三个正整数,两个数字之间用空格隔开,三个正整数分别表示某一种道具的数量、单个道具的价格和魅力值。
输出
每组测试数据的输出只有一行,即道具魅力值的最大和。
样例输入 Copy
3 10
2 2 3
1 5 10
2 4 12
样例输出 Copy
27
while True:
try:
n, c = map(int, input().split())
n_items = []
for _ in range(n):
n_item = list(map(int, input().split()))
n_items.append(n_item)
w1 = []
v1 = []
for item in n_items:
w1 += [item[1]] * item[0] # 按数量添加价格
v1 += [item[2]] * item[0] # 按数量添加价值
n = len(w1)
dp = [[0 for _ in range(c + 1)] for _ in range(n + 1)]
w1.insert(0, 0)
v1.insert(0, 0)
for i in range(1, n + 1):
for j in range(1, c + 1):
if w1[i] <= j:
dp[i][j] = max(dp[i - 1][j], (dp[i - 1][j - w1[i]] + v1[i]))
else:
dp[i][j] = dp[i - 1][j]
print(dp[n][c])
except EOFError:
break
为什么上面的代码放在oj上运行,运行出错?我的思路是接近0-1背包问题来实现多重背包问题。