题解 | 【模板】01背包 Python3

import sys
# 0/1背包
# 动态规划，dp1[i][j]为考虑到第i个物品，容量为j的背包的最大价值，不考虑背包是否装满
# dp2[i][j] 考虑装满的情况下
# dp[i][j] = max(dp[i][j-v]+w,dp[i-1][j])
# dp1 和 dp2主要是初始化条件不同和一些遍历逻辑
# dp2要考虑到完全背包，比如主要结果dp2[i][j]是表示考虑到所有所有物品后完全背包的最大价值
# 那么 dp2[i][j] = max(dp2[i][j-v]+w,dp2[i-1][j]), 但是可能dp2[i][j-v]并没有一个完全背包解，因此需要有一个值来表征，用一个很小的值

min_w = - 1000 * 1000 - 1

n, V = list(map(int, input().strip().split()))

data = []

for i in range(n):
    v, w = list(map(int, input().strip().split()))
    data.append([v,w])

dp1 = [[0]*(V+1) for _ in range(n+1)]
dp2 = [[min_w]*(V+1) for _ in range(n+1)]
for i in range(n+1):
    dp2[i][0] = 0
# dp2以min_w初始化表征不可达状态，只有dp2[i][0]为0，表示体积完全占用

# 因为只和当前行计算只和上一行有关系，其实一维dp也行

for i in range(1,n+1):
    v, w = data[i-1]
    for j in range(1,V+1):
        if j < v:
            dp1[i][j] = dp1[i-1][j]
        else:
            dp1[i][j] = max(dp1[i-1][j-v]+w, dp1[i-1][j])



for i in range(1,n+1):
    v, w = data[i-1]
    for j in range(1,V+1):
        if j < v:
            dp2[i][j] = dp2[i-1][j]
        else:
            dp2[i][j] = max(dp2[i-1][j-v]+w, dp2[i-1][j])

print(dp1[-1][-1])
print(dp2[-1][-1] if dp2[-1][-1]>=1 else 0)