Python3使用动态规划处理背包问题：完全背包（含背包恰好装满的情况）_完全背包问题python

完全背包问题是基于01背包的，如果对01背包问题不熟悉，可以参考： Python3使用动态规划处理01背包问题

题目介绍

• 原题链接：NC309 完全背包
• 描述
  你有一个背包，最多能容纳的体积是V。
  现在有n种物品，每种物品有任意多个，第i种物品的体积为$v_i$ ,价值为$w_i$。
  （1）求这个背包至多能装多大价值的物品？
  （2）若背包恰好装满，求至多能装多大价值的物品？
• 数据范围：$1\le v,v_i,w_i\le 1000$
• 示例1
  输入：

  6,2,[[5,10],[3,1]]
  1

  返回值：[10,2]
• 示例2
  输入：

  8,3,[[3,10],[9,1],[10,1]]
  1

  返回值：[20,0]
  说明：无法恰好装满背包
• 示例3
  输入：

  13,6,[[13,189],[17,360],[19,870],[14,184],[6,298],[16,242]]
  1

  返回值：[596,189]
  说明：可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189

题解1

问题1和问题2的求解过程基本一致 ，不同的是在动态规划初始化数组时，在求解问题1时其所对应的动态规划数组全部为0，在求解问题2时其所对应的动态规划数组只有第一个元素为0其余的为负无穷。之所以将动态规划数组里的元素设为负无穷，是为了进行阻断。在从前至后推进时如果在填充了当前元素后还有剩余空间，那么之前扫描过的其他元素若不能恰好填满剩余空间，则这个元素将无法被成功填充（表征为：负无穷加上一个常数还是负无穷），即这种情况将会被阻断。

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]}]')
1
2
3
4
5
6
7
8
9
10
11

题解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}]')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

题解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}]')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18