题解 | #完全背包#

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

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

题解1：

v, n, nums = 1, 1, []
exec('v, n, nums = ' + input())
dp1 = [0 for i in range(v + 1)]
dp2 = [float('-inf') for j in range(v+1)]
dp2[0] = 0
for i in range(1, n+1):
    for j in range(1, v+1):
        if j >= nums[i-1][0]:
            dp1[j] = max(dp1[j], nums[i-1][1] + dp1[j-nums[i-1][0]])
            dp2[j] = max(dp2[j], nums[i-1][1] + dp2[j-nums[i-1][0]])
print(f'[{dp1[v]},{0 if dp2[v] < 0 else dp2[v]}]')

题解2：

v, n, nums = 1, 1, []
exec('v, n, nums = ' + input())
dp = [0 for i in range(v+1)]
dp1 = [0 for j in range(v+1)]
for i in range(1, v+1):
    _max = float('-inf')
    max1 = float('-inf')
    for j in range(n):
        if i >= nums[j][0]:
            _max = max(_max, dp[i-nums[j][0]]+nums[j][1])
            max1 = max(max1, dp1[i-nums[j][0]]+nums[j][1])
        _max = max(_max, dp[i-1])
    dp[i] = _max
    dp1[i] = max1
res = 0 if dp1[v] < 0 else dp1[v]
print(f'[{dp[v]},{res}]')

题解3：

v, n, nums = 1, 1, []
exec('v, n, nums = ' + input())
V = [0 for i in range(n+1)]
W = [0 for j in range(n+1)]
for goods in range(1, n+1):
    V[goods] = nums[goods-1][0]
    W[goods] = nums[goods-1][1]
dp1 = [0 for i in range(v+1)]
dp2 = [float('-inf') for j in range(v+1)]
dp2[0] = 0
for goods in range(1, n+1):
    for capacity in range(V[goods], v+1):
        dp1[capacity] = max(dp1[capacity], dp1[capacity - V[goods]] + W[goods])
        dp2[capacity] = max(dp2[capacity], dp2[capacity - V[goods]] + W[goods])
    if dp2[capacity] < 0:
        dp2[capacity] = float('-inf')
res = 0 if dp2[v] == float('-inf') else dp2[v]
print(f'[{dp1[v]},{res}]')