题解 | 【模板】01背包

import sys

line = sys.stdin.readline().strip()
n,V = map(int,line.split())
Mat = []
for _ in range(n):
    line = sys.stdin.readline().strip()
    Mat.append(list(map(int,line.split())))
dp = [[0 for i in range(V+1)] for j in range(n+1)]

for i in range(1, n+ 1):
    for j in range(1, V+1):
        dp[i][j] = dp[i-1][j]
        vv = Mat[i - 1][0]
        ww = Mat[i - 1][1]
        if j < vv: continue
        dp[i][j] = max(dp[i - 1][j - vv] + ww, dp[i][j])
print(dp[n][V])
# 上面是不装满, 下面是装满


dp = [[0 for i in range(V+1)] for j in range(n+1)]
for i in range(1, n+ 1):
    for j in range(1, V+1):
        dp[i][j] = dp[i-1][j]
        vv = Mat[i - 1][0]
        ww = Mat[i - 1][1]
        if j < vv: continue
        elif j - vv == 0:
            dp[i][j] = max(dp[i - 1][j - vv] + ww, dp[i][j])
        elif j - vv != 0 and dp[i - 1][j - vv] != 0:
            dp[i][j] = max(dp[i - 1][j - vv] + ww, dp[i][j])
print(dp[n][V])

有几率超时，卡着过的

dp 原来01背包比无限背包复杂一点，01背包要开二维数组，用一维数组会抽象点