算法:动态规划|背包问题②|完全背包问题的问题转化思路与优化(python实现)

算法:动态规划|背包问题②|完全背包问题的问题转化思路与优化(python实现)

九月 06, 2019
当前设备屏幕尺寸过小，推荐使用PC模式浏览。

写在前面

问题描述

有一个重量上限容量为 totaltotal 的背包和 item_numitem\_num 种物品，第 ii 种物品的重量是 wiw_i 、价值为 viv_i ，求问选择将哪些物品放入背包(每种物品的数量无限)可以得到最大的价值。

附带约束：背包恰好装满，解决方案参见 [算法][动态规划][背包问题①]0-1背包问题的优化及约束变形[python实现]：算法约束-恰好放满背包

问题求解

向0-1背包问题转化

在01背包问题中我们推断了01背包算法的动态转移方程：

dp[i+1][j]=max{dp[i][j−wi]+vi,dp[i][j]}dp[i+1][j]=max\{dp[i][j-w_i]+v_i,dp[i][j]\}

在逆序推断的情况下，该动态转移矩阵可以略去一个维度变为:

dp[j]=max{dp[j−wi]+vi,dp[j]}dp[j]=max\{dp[j-w_i]+v_i, dp[j]\}

修正逆序遍历的下限 lower=max{total−∑t=iitem_numwt),w[i]}lower=max\{total-\sum_{t=i}^{item\_num}w_t), w[i]\} 之后，算法的伪码为：

1
2
3
4
def zero_one_solution(...):
    for(int i = 0; t < item_num; i++): # 物品循环
        for(int j = total; j >= lower; j--): # 价值循环(采用逆循环的方式)
            dp[j]=max(dp[j - w[i]] + v[i], dp[j])
  • 考虑第ii种物品，显然其最大可选择个数为k=⌊totalwi⌋k=⌊\frac{total}{w_i}⌋，我们完全可以把第 ii 种物品重复 kk 次放入原w和v数组中，将问题转化为0-1背包问题。

因此算法框架就变为：

1
2
3
4
def complete_solution(..., w, v):  # 将完全背包问题转化为0-1背包问题的算法结构
    w, v = encoder(w, v)
    result = zero_one_solution(..., w, v)
    result = decoder(result)  # 如果不需要对package_trace解码，可以跳过这一步骤，详见前续Ⅱ

基于掩码的优化

在完全背包问题中，由于每种物品的数量无限，我们很容易观察到两个常数级别的优化：

  • 若两件物品 xx 和 yy 满足 wx≤wyw_x\le w_y 且 vx≥vyv_x \ge v_y ，即物品 xx 比物品 yy 又轻又贵重，则物品 yy 实际上将永不被考虑放入背包。
  • 若物品 xx 的重量 wx>totalw_x>total，物品 xx 将永不被考虑放入背包。

给定一个掩码数组mask[item_num]，当其等于 1 时直接进行跳过该物品，即：

1
2
3
4
5
6
for(int i = 0; t < item_num; i++): # 物品循环
    if mask[i] == 1:
        continue
    # else do other thing like :
    # {for(int j = total; j >= lower; j--): dp[j]=max(...)}
    # or {w, v = encode(...)}(will be introduced next section)

产生掩码的代码：(完整代码@码云)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# def get_mask(...):
# input total:Scale, w:List, v:List
item_num= len(w)
mask = [0 for _1 in range(item_num + 1)]
for i in range(item_num):  # 产生掩码 复杂度为 O(item_num^2)
    if w[i] > total:  # w_x>total直接跳过
        mask[i] = 1
        continue
    for j in range(i + 1, item_num, 1):  # 基于冒泡的形式进行比较
        if mask[i] == 1:  # 稍微进行加速
            break
        a, b = w[i] <= w[j], v[i] >= v[j]
        c, d = w[i] >= w[j], v[i] <= v[j]
        picked = j if a and b else (i if c and d else -1)
        if picked > 0:
            mask[picked] = 1
            break
# output mask:List

编码和解码

编码和解码，即通过编码w和v把完全背包问题转化为0-1背包问题。

完全编码

  • 考虑第ii种物品，显然其最大可选择个数为k=⌊totalwi⌋k=⌊\frac{total}{w_i}⌋，我们完全可以把第 ii 种物品重复 kk 次放入原w和v数组中，将问题转化为0-1背包问题。这种编码方式被称为full编码方式。
  • 算法时间复杂度为 O(total∗item_num∗∑totalwi)O(total*item\_num*\sum \frac{total}{w_i}) 。

编码方式很简单：(完整代码@码云)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def encoder(total, w_o, v_o):
    """
    采用全量编码的方式重组物品序列
    :param total: 背包容量上限
    :param w_o: 原物品序列重量列表
    :param v_o: 原物品序列价值列表
    :return: 编码后的物品序列价值列表
    """
    item_num, w, v, mask = len(w_o), [], [], get_mask(total, w_o, v_o)

    for i in range(item_num):
        if mask[i] == 1:
            continue
        size = max(total // w_o[i], 1)  #  至少应该保留一件防止程序bug
        # 全量输出模式 : 添加 ⌊total/v[i]⌋ 件相同的物品
        w += [w_o[i] for _ in range(size)]
        v += [v_o[i] for _ in range(size)]
    return w, v, mask

解码方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def decoder(w_o, trace_o, mask):
    """
    采用全量编码的方式重组物品序列
    :param w_o: 原物品序列重量列表
    :param trace_o: 原物品序列选择列表
    :param mask: 过滤掩码，当其等于 1 时直接进行跳过该物品
    :return: 编码后的物品选择列表
    """
    item_num, trace, start = len(w_o), [], 0
    for i in range(item_num):
        if mask[i] == 1:
            continue
        size = max(total // w_o[i], 1)  # 为了trace可追踪，至少为1件
        num = len(list(filter(lambda x: start <= x < start + size, trace_o)))
        if num > 0:
            trace += [(i, num)]  # (i, j) ： 序号为 i 的物品放入 j 个
        start += size
    return trace

压缩编码/二进制编码

  • 考虑一种新的编码方式：二进制编码。对于s∈Ns \in \N，ss 取遍满足2s≤totalwi2^s\le \frac{total}{w_i} 的自然数，将原本的k=⌊totalwi⌋k=⌊\frac{total}{w_i}⌋下降为对数级别：k=log⁡⌊totalwi⌋k=\log⌊\frac{total}{w_i}⌋，同时重构 wiw_i 和 viv_i 为{wi∗20,⋯ ,wi∗2s}\{w_i*2^0, \cdots, w_i*2^s\}、{vi∗20,⋯ ,vi∗2s}\{v_i*2^0, \cdots , v_i*2^s\}的序列。这种编码方式被称为compress编码方式或binary编码方式。

例如，对于物品xx有 wx=2w_x=2，vx=1v_x=1，背包容量为9，将该种物品重构为序号从0起至 smax=log⁡⌊totalwi⌋=2s_{max}=\log ⌊\frac{total}{w_i}⌋=2 即 k=smax+1k=s_{max}+1 个的新物品序列：

物品编号(s) 物品重量 物品价值 选中该编码后的物品代表的原物品数
0 2 1 202^0=1
1 4 2 212^1=2
2 8 4 222^2=4

Tip：在完全编码中需要编码为 44 个wx=2w_x=2，vx=1v_x=1的物品，转为0-1背包问题。显然压缩编码模式。

  • 在二进制编码后物品序列中，选择编号为 ss 的二进制物品时，即代表了选择了 2s2^s 个原物品。例如已知原本可以选择0~4个原物品，若选择3个原物品，在二进制物品列表中即为选择中 s={0,1}s =\{0,1\}的两个物品。
  • 算法时间复杂度从完全编码的 O(total∗item_num∗∑totalwi)O(total*item\_num*\sum \frac{total}{w_i}) 下降到了 O(total∗item_num∗∑log⁡totalwi)O(total*item\_num*\sum \log\frac{total}{w_i}) 。

编码方式：(完整代码@码云)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def encoder(total, w_o, v_oe):
    """
    采用全量编码的方式重组物品序列
    :param total: 背包容量上限
    :param w_o: 原物品序列重量列表
    :param v_o: 原物品序列价值列表
    :return: 编码后的物品序列价值列表
    """
    item_num, w, v, mask = len(w_o), [], [], get_mask(total, w_o, v_o)

    for i in range(item_num):
        if mask[i] == 1:
            continue
        size = size_counter(w_o[i])
        # 压缩模式 : 添加 ⌊log(total/v[i])⌋ 件相同的物品
        w += [w_o[i] * (2 ** _) for _ in range(size)]
        v += [v_o[i] * (2 ** _) for _ in range(size)]
    return w, v, mask

解码方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def decoder(w_o, trace_o, mask, w):
    """
    采用全量编码的方式重组物品序列
    :param w_o: 原物品序列重量列表
    :param trace_o: 原物品序列选择列表
    :param mask: 过滤掩码，当其等于 1 时直接进行跳过该物品
    :param w: 编码后的物品序列列表，用于解码
    :return: 编码后的物品选择列表
    """
    import math
    item_num, trace, start = len(w_o), [], 0
    for i in range(item_num):
        if mask[i] == 1:
            continue
        size = max(math.floor(math.log(total / w_o[i], 2)) + 1, 1)  # 为了trace可追踪，至少为1件
        num, codes = 0, list(filter(lambda x: start <= x < start + size, trace_o))
        for v in codes:
            num += w[v] // w_o[i]
        if num > 0:
            trace += [(i, num)]# (i, j) ： 序号为 i 的物品放入 j 个
        start += size
    return trace

基于状态转移的速度优化

我们发现，哪怕是基于二进制编码，算法的时间复杂度还是O(total∗item_num∗∑log⁡totalwi)O(total*item\_num*\sum \log\frac{total}{w_i})，跟0-1背包问题的O(total∗item_num)O(total*item\_num)仍有差距。
我们再次写出0-1背包问题在逆序情况下的状态转移方程

dp[j]=max{dp[j−wi]+vi,dp[j]}dp[j]=max\{dp[j-w_i]+v_i, dp[j]\} 

1
2
3
4
for i in range(item_num):
    for j in range(total, w[i]-1, -1):  # 倒序遍历背包剩余容量，即 for(inr j = total; j >= w[i]; j--)
        # dp[i+1][j] = max(dp[i][j-w[i]]+v[i], dp[i][j]) , also works
        dp[j] = dp[j - w[i]] + v[i]

稍微修改一下遍历方向：

1
2
3
4
for i in range(item_num):
    for j in range(w[i], total+1, 1):  # 正序遍历背包剩余容量，即 for(inr j = w[i]; j <= total; j++)
        # dp[i+1][j] = max(dp[i+1][j-w[i]]+v[i], dp[i][j]) , also works
        dp[j] = dp[j - w[i]] + v[i]

会发现完全背包问题居然得解了，且算法的时间复杂度为：O(total∗item_num)O(total*item\_num)。

为什么这么做会有作用呢？回忆0-1背包问题中我们倒序遍历背包容量之所以能减少一个dp维度的原因：
当我们从后往前遍历时，确保了后一个状态i是由前一个状态i-1递推而来。后一个状态经过更新之后前一个状态的更新并不会造成后一个状态的改变，即前一个状态i-1永远不会选到状态i所对应的物品i，也就是为了保证一种物品只选一次，即完全背包的状态转移方程应当是(正序遍历和倒序遍历时下式应当都成立)：

dp[i+1][j]=max{dp[i+1][j−wi]+vi,dp[i][j]}dp[i+1][j]=max\{dp[i+1][j-w_i]+v_i, dp[i][j]\}

完全背包问题的最优解决方案

基于状态转移的速度优化方案，我们给出以下代码：(完整代码@码云)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def solution_speedup(data, restrict=True):
    """
    完全背包问题(兼容约束解决方案)
    空间复杂度 O(total)，时间复杂度 O(total*item_num)
    :param data: 数据集
    :param restrict: 是否进行装满约束 @see https://blog.csdn.net/Shenpibaipao/article/details/90961776#_182
    :return: 最优价值和放入背包的物品序号
    """
    total, w, v, answer = data.values()
    item_num, mask = len(w), get_mask(total, w, v)
    specific = float("-inf") if restrict else 0  # 兼容满背包约束方案
    dp = [specific for _1 in range(total + 1)]
    dp[0] = 0
    trace = [[] for _1 in range(total + 1)]

    for i in range(item_num):
        if mask[i] == 1:
            continue
        for j in range(w[i], total+1, 1):  # 修改此处以实现完全背包 -> for(i=w[i];i<=total;i++)
            trace[j], dp[j] = (trace[int(j - w[i])] + [i], dp[j - w[i]] + v[i]) \
                if dp[j - w[i]] + v[i] > dp[j] else (trace[j], dp[j])

    # 重新编码轨迹，如果不需要输出轨迹或重编译轨迹可直接注释下面这一段代码以加速算法运行
    temp_trace, trace[total] = trace[total], []
    for i in range(len(temp_trace)):
        v = temp_trace[i]
        if i > 0 and temp_trace[i-1] == v:  # 依赖逻辑短路保证数组不越界
            continue
        trace[total] += [(v, temp_trace.count(v))]

    return {
        "max_value": dp[total],
        "package_trace": trace[total]
    }

完整代码测试

这里给出以上所有代码和测试：(完整代码@码云)

01-package.py测试结果：

1
2
3
4
function[solution_full] {'max_value': 30, 'package_trace': [(0, 5)]} while repeat 5000 times, using time: 56.75(s)
function[solution_compress] {'max_value': 30, 'package_trace': [(0, 5)]} while repeat 5000 times, using time: 31.78(s)
function[solution_compress] {'max_value': 10, 'package_trace': [(0, 1), (1, 2)]} while repeat 1 times, using time: 0.42(s)
function[solution_speedup] {'max_value': 17, 'package_trace': [(2, 1), (5, 2)]} while repeat 5000 times, using time: 12.58(s)

可以看到solution_speedup的速度得到显著的提升。

> 点此下载代码

> 点此下载讲义

  1. 1. 问题描述
  2. 2. 问题求解
    1. 2.1. 向0-1背包问题转化
    2. 2.2. 基于掩码的优化
    3. 2.3. 编码和解码
      1. 2.3.1. 完全编码
      2. 2.3.2. 压缩编码/二进制编码
    4. 2.4. 基于状态转移的速度优化
      1. 2.4.1. 完全背包问题的最优解决方案
  3. 3. 完整代码测试