第一行输入两个整数
和
,分别表示物品数量与背包容量。
此后
行,第
行输入两个整数
,分别表示第
件物品的体积与价值。
输出两行:
第一行输出方案
的答案;
第二行输出方案
的答案(若无解输出
)。
3 5 2 10 4 5 1 4
14 9
在该组样例中:
选择第
、第
件物品即可获得最大价值
(未装满);
选择第
、第
件物品可使背包体积
恰好装满且价值最大,为
。
3 8 12 6 11 8 6 8
8 0
装第三个物品时总价值最大但是不满,装满背包无解。
要求
的时间复杂度,
空间复杂度。
def ans(): n, v = map(int, input().split(" ")) size , worth = [0 for _ in range(n)] , [0 for _ in range(n)] for i in range(n): size[i] , worth[i] = map(int, input().split(" ")) dp1 = [0 for _ in range(v+1)] dp2 = [float("-inf") for _ in range(v+1)] dp2[0] = 0 for i in range(n): for j in range(v,0,-1): if j >= size[i]: dp1[j] = max(dp1[j - size[i]] + worth[i] , dp1[j]) dp2[j] = max(dp2[j - size[i]] + worth[i] , dp2[j]) print(dp1[-1]) res = 0 if dp2[-1] == float("-inf") else dp2[-1] print(res) ans()