题解 | #【模板】01背包#

01背包问题可用二维 dp，在遍历状态转移时，由于状态只与其中一个维度有关，可进行压缩;注意恰好装满，初始数组值为 -inf。 代码如下:

n, v = map(int, input().strip().split())
dp_1 = [0 for _ in range(v + 1)]
dp_2 = [float('-inf') for _ in range(v + 1)]
q, w = [], []
dp_2[0] = 0
for _ in range(n):
    qi, wi = map(int, input().strip().split())
    q.append(qi)
    w.append(wi)
for i in range(n):
    for j in range(v, q[i] - 1, -1):
        dp_1[j] = max(dp_1[j], dp_1[j - q[i]] + w[i])
        dp_2[j] = max(dp_2[j], dp_2[j - q[i]] + w[i])
print(dp_1[-1])
print(dp_2[-1] if dp_2[-1] != float('-inf') else 0)