题解 | #NC145 01背包#

这里只放了答案，如果需要详细的步骤解析（有视频教程讲解），可以参考Python3使用动态规划处理01背包问题

另外我没有使用题目中自带的类名，而还是采用的打印的方式进行，关于解包变量可以参考：Python3使用exec函数将输入进来的结果的字符串的值解包成变量的值

题解1：二维列表

V, n, vw = 1, 1, []
exec('V, n, vw = ' + input())
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):
        if vw[i-1][0] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], vw[i-1][1]+dp[i-1][j-vw[i-1][0]])
print(dp[-1][-1])

题解2：一维列表（滚动数组）

V, n, vw = 1, 1, []
exec('V, n, vw = ' + input())
dp = [0 for j in range(V+1)]
for i in range(1, n+1):
    for j in range(V, 0, -1):
        if j >= vw[i-1][0]:
            dp[j] = max(dp[j], vw[i-1][1]+dp[j-vw[i-1][0]])
print(dp[-1])