跳至主要內容

03. 背包问题知识(三)

ITCharge大约 8 分钟

背包问题知识(三)

4. 多重背包问题

多重背包问题:有 nn 种物品和一个最多能装重量为 WW 的背包,第 ii 种物品的重量为 weight[i]weight[i],价值为 value[i]value[i],件数为 count[i]count[i]。请问在总重量不超过背包载重上限的情况下,能装入背包的最大价值是多少?

4.1 多重背包问题基本思路

我们可以参考「0-1 背包问题」的状态定义和基本思路,对于容量为 ww 的背包,最多可以装 min{count[i1],wweight[i1]}min \lbrace count[i - 1], \frac{w}{weight[i - 1]} \rbrace 件第 i1i - 1 件物品。那么我们可以多加一层循环,枚举第 i1i - 1 件物品可以选择的件数(0min{count[i1],wweight[i1]}0 \sim min \lbrace count[i - 1], \frac{w}{weight[i - 1]} \rbrace),从而将「完全背包问题」转换为「0-1 背包问题」。

思路 1:动态规划 + 二维基本思路

1. 划分阶段

按照物品种类的序号、当前背包的载重上限进行阶段划分。

2. 定义状态

定义状态 dp[i][w]dp[i][w] 表示为:前 ii 种物品放入一个最多能装重量为 ww 的背包中,可以获得的最大价值。

状态 dp[i][w]dp[i][w] 是一个二维数组,其中第一维代表「当前正在考虑的物品种类」,第二维表示「当前背包的载重上限」,二维数组值表示「可以获得的最大价值」。

3. 状态转移方程

dp[i][w]=max{dp[i1][wk×weight[i1]]+k×value[i1]},0kmin{count[i1],wweight[i1]}dp[i][w] = max \lbrace dp[i - 1][w - k \times weight[i - 1]] + k \times value[i - 1] \rbrace, \quad 0 \le k \le min \lbrace count[i - 1], \frac{w}{weight[i - 1]} \rbrace

4. 初始条件
  • 如果背包载重上限为 00,则无论选取什么物品,可以获得的最大价值一定是 00,即 dp[i][0]=0,0isizedp[i][0] = 0, 0 \le i \le size
  • 无论背包载重上限是多少,前 00 种物品所能获得的最大价值一定为 00,即 dp[0][w]=0,0wWdp[0][w] = 0, 0 \le w \le W
5. 最终结果

根据我们之前定义的状态,dp[i][w]dp[i][w] 表示为:前 ii 种物品放入一个最多能装重量为 ww 的背包中,可以获得的最大价值。则最终结果为 dp[size][W]dp[size][W],其中 sizesize 为物品的种类数,WW 为背包的载重上限。

思路 1:代码

class Solution:
    # 思路 1:动态规划 + 二维基本思路
    def multiplePackMethod1(self, weight: [int], value: [int], count: [int], W: int):
        size = len(weight)
        dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 枚举背包装载重量
            for w in range(W + 1):
                # 枚举第 i - 1 种物品能取个数
                for k in range(min(count[i - 1], w // weight[i - 1]) + 1):
                    # dp[i][w] 取所有 dp[i - 1][w - k * weight[i - 1] + k * value[i - 1] 中最大值
                    dp[i][w] = max(dp[i][w], dp[i - 1][w - k * weight[i - 1]] + k * value[i - 1])
                    
        return dp[size][W]

思路 1:复杂度分析

  • 时间复杂度O(n×W×C)O(n \times W \times C),其中 nn 为物品种类数量,WW 为背包的载重上限,CC 是物品的数量数组长度。因为 n×C=count[i]n \times C = \sum count[i],所以时间复杂度也可以写成 O(W×count[i])O(W \times \sum count[i])
  • 空间复杂度O(n×W)O(n \times W)

4.2 多重背包问题滚动数组优化

在「完全背包问题」中,我们通过优化「状态转移方程」的方式,成功去除了对物品件数 kk 的依赖,从而将时间复杂度下降了一个维度。

而在「多重背包问题」中,我们在递推 dp[i][w]dp[i][w] 时,是无法从 dp[i][wweight[i1]]dp[i][w - weight[i - 1]] 状态得知目前究竟已经使用了多个件第 i1i - 1 种物品,也就无法判断第 i1i - 1 种物品是否还有剩余数量可选。这就导致了我们无法通过优化「状态转移方程」的方式将「多重背包问题」的时间复杂度降低。

但是我们可以参考「完全背包问题」+「滚动数组优化」的方式,将算法的空间复杂度下降一个维度。

思路 2:动态规划 + 滚动数组优化

1. 划分阶段

按照当前背包的载重上限进行阶段划分。

2. 定义状态

定义状态 dp[w]dp[w] 表示为:将物品装入最多能装重量为 ww 的背包中,可以获得的最大价值。

3. 状态转移方程

dp[w]=max{dp[wk×weight[i1]]+k×value[i1]},0kmin{count[i1],wweight[i1]}dp[w] = max \lbrace dp[w - k \times weight[i - 1]] + k \times value[i - 1] \rbrace, \quad 0 \le k \le min \lbrace count[i - 1], \frac{w}{weight[i - 1]} \rbrace

4. 初始条件
  • 无论背包载重上限为多少,只要不选择物品,可以获得的最大价值一定是 00,即 dp[w]=0,0wWdp[w] = 0, 0 \le w \le W
5. 最终结果

根据我们之前定义的状态, dp[w]dp[w] 表示为:将物品装入最多能装重量为 ww 的背包中,可以获得的最大价值。则最终结果为 dp[W]dp[W],其中 WW 为背包的载重上限。

思路 2:代码

class Solution: 
    # 思路 2:动态规划 + 滚动数组优化
    def multiplePackMethod2(self, weight: [int], value: [int], count: [int], W: int):
        size = len(weight)
        dp = [0 for _ in range(W + 1)]
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 逆序枚举背包装载重量(避免状态值错误)
            for w in range(W, weight[i - 1] - 1, -1):
                # 枚举第 i - 1 种物品能取个数
                for k in range(min(count[i - 1], w // weight[i - 1]) + 1):
                    # dp[w] 取所有 dp[w - k * weight[i - 1]] + k * value[i - 1] 中最大值
                    dp[w] = max(dp[w], dp[w - k * weight[i - 1]] + k * value[i - 1])
                
        return dp[W]

思路 2:复杂度分析

  • 时间复杂度O(n×W×C)O(n \times W \times C),其中 nn 为物品种类数量,WW 为背包的载重上限,CC 是物品的数量数组长度。因为 n×C=count[i]n \times C = \sum count[i],所以时间复杂度也可以写成 O(W×count[i])O(W \times \sum count[i])
  • 空间复杂度O(W)O(W)

4.3 多重背包问题二进制优化

在「思路 2」中,我们通过「滚动数组优化」的方式,降低了算法的空间复杂度。同时也提到了无法通过优化「状态转移方程」的方式将「多重背包问题」的时间复杂度降低。

但我们还是可以从物品数量入手,通过「二进制优化」的方式,将算法的时间复杂度降低。

二进制优化:简单来说,就是把物品的数量 count[i]count[i] 拆分成「由 1,2,4,,2m1, 2, 4, …, 2^m 件单个物品组成的大物品」,以及「剩余不足 22 的整数次幂数量的物品,由 count[i]2log2(count[i]+1)1count[i] -2^{\lfloor \log_2(count[i] + 1) \rfloor - 1} 件单个物品组成大物品」。

举个例子,第 ii 件物品的数量为 3131,采用「二进制优化」的方式,可以拆分成 31=1+2+4+8+1631 = 1 + 2 + 4 + 8 + 16 一共 55 件物品。也将是将 3131 件物品分成了 55 件大物品:

  1. 11 件大物品有 11 件第 ii 种物品组成;
  2. 22 件大物品有 22 件第 ii 种物品组成;
  3. 33 件大物品有 44 件第 ii 种物品组成;
  4. 44 件大物品有 88 件第 ii 种物品组成;
  5. 55 件大物品有 1616 件第 ii 种物品组成。

55 件大物品通过不同的组合,可表达出第 ii 种物品的数量范围刚好是 0310 \sim 31

这样本来第 ii 件物品数量需要枚举共计 3232 次(0310 \sim 31),而现在只需要枚举 55 次即可。

再举几个例子:

  1. ii 件物品的数量为 66,可以拆分为 6=1+2+36 = 1 + 2 + 3 一共 33 件物品。
  2. ii 件物品的数量为 88,可以拆分为 8=1+2+4+18 = 1 + 2 + 4 + 1 一共 44 件物品。
  3. ii 件物品的数量为 1818,可以拆分为 18=1+2+4+8+318 = 1 + 2 + 4 + 8 + 3 一共 55 件物品。

经过「二进制优化」之后,算法的时间复杂度从 O(W×count[i])O(W \times \sum count[i]) 降到了 O(W×log2count[i])O(W \times \sum \log_2{count[i]})

思路 3:动态规划 + 二进制优化

1. 划分阶段

按照当前背包的载重上限进行阶段划分。

2. 定义状态

定义状态 dp[w]dp[w] 表示为:将物品装入最多能装重量为 ww 的背包中,可以获得的最大价值。

3. 状态转移方程

dp[w]=max{dp[wweightnew[i1]]+valuenew[i1]}dp[w] = max \lbrace dp[w - weight \underline{ } new[i - 1]] + value \underline{ } new[i - 1] \rbrace

4. 初始条件
  • 无论背包载重上限为多少,只要不选择物品,可以获得的最大价值一定是 00,即 dp[w]=0,0wWdp[w] = 0, 0 \le w \le W
5. 最终结果

根据我们之前定义的状态, dp[w]dp[w] 表示为:将物品装入最多能装重量为 ww 的背包中,可以获得的最大价值。则最终结果为 dp[W]dp[W],其中 WW 为背包的载重上限。

思路 3:代码

class Solution:
    # 思路 3:动态规划 + 二进制优化
    def multiplePackMethod3(self, weight: [int], value: [int], count: [int], W: int):
        weight_new, value_new = [], []
        
        # 二进制优化
        for i in range(len(weight)):
            cnt = count[i]
            k = 1
            while k <= cnt:
                cnt -= k
                weight_new.append(weight[i] * k)
                value_new.append(value[i] * k)
                k *= 2
            if cnt > 0:
                weight_new.append(weight[i] * cnt)
                value_new.append(value[i] * cnt)
        
        dp = [0 for _ in range(W + 1)]
        size = len(weight_new)
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 逆序枚举背包装载重量(避免状态值错误)
            for w in range(W, weight_new[i - 1] - 1, -1):
                # dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight_new[i - 1] 的背包中,再装入第 i - 1 物品所得的最大价值」两者中的最大值
                dp[w] = max(dp[w], dp[w - weight_new[i - 1]] + value_new[i - 1])
                    
        return dp[W]

思路 3:复杂度分析

  • 时间复杂度O(W×log2count[i])O(W \times \sum \log_2{count[i]}),其中 WW 为背包的载重上限,count[i]count[i] 是第 ii 种物品的数量。
  • 空间复杂度O(W)O(W)

参考资料