算法:动态规划|背包问题①|0-1背包问题的优化及约束变形(python实现)

算法:动态规划|背包问题①|0-1背包问题的优化及约束变形(python实现)

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

写在前面

题目描述

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

问题求解

A.动态过程

动态规划的精髓在于拆解大问题为子问题。我们给定一种数据结构dp[item_num][total]，其中,dp[i][j]表示第i+1次尝试把物品i放入背包后，背包剩余容量为j，此时背包中的物品总价值为dp[i][j]。

Tip:物品的序数从0计起，放入背包的动作过程从第1次计起。

由于每次尝试把物品放入背包的过程是一个动态过程，其动态转移方程为:

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]\}

显然i是主要的状态转移量：

1
2
3
4
5
6
7
8
9
for i in range(item_num):  # 第i+1次尝试放入第i个物品(物品序号从0起||显然，尝试次数从1起,即i+1)
    # 以下是动态转移过程
    for j in range(total, -1, -1):  # 倒序遍历背包剩余容量，即 for(inr j = total; j>=0; j--)
        dp[i+1][j] = max(dp[i][j-w[i]]+v[i],dp[i][j]) if j >= w[i] else dp[i][j]
        # 等价于:
        # if j >= w[i] and dp[i][j-w[i]] + v[i] > dp[i][j]:  # 第[i+1]次尝试放入时选择放入第[i]个物品
        #     dp[i+1][j] = dp[i][j-w[i]] + v[i]  # 更新第i+1次尝试放入的推测值(物品总价值)
        # else:  # 跳过物品，不考虑放入该物品，拷贝"前[i]次尝试放入"的堆栈数据到[i+1]上
        #     dp[i+1][j] = dp[i][j]

即，第i+1次考虑要不要把第i个物品放入背包(0-1问题中恰好nn个物品最多只考虑nn次"放不放"的问题)，知道它的重量 wiw_i 和价值 viv_i，当dp[i][j-w[i]] + v[i] > dp[i][j]，即前一次(dp[i][~])考虑时，没有放入wiw_i重量的物品时的价值(dp[i][j-w[i]])加上当前物品的价值viv_i大于前一次考虑时放入wiw_i重量的物品时的价值(dp[i][j])，则选择放入背包。

B.代码求解

首先，给出我们的数据集：

1
2
3
4
5
6
7
8
9
10
11
12
13
datasets = [
    {
        "total": 8,  # total capacity(weight)
        "weight": [2, 3, 4, 5],  # item weight
        "value": [3, 4, 5, 6],  # item value
        "answer": {  # this is just for testing, can be ignored
            "max_value": 10,
            "package_trace": [1, 3]  # index of item
        }
    },{
    ......
    }
]

在1.1的分析基础上，我们引入一个新的数据栈trace，用于记录最优解中所放物品的序号列表，其动态转移过程与dp一致。
于是该问题就很容易得到解答了：(完整代码@码云)

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
def solution(data):
    """
    基于动态规划解 0-1 背包问题
    :param data: 数据集
    :return: 最优价值和放入背包的物品序号
    """
    total, w, v, answer = data.values()
    item_num = len(w)  # item_num 个物品，至多放 item_num 次
    # dp[第i次尝试放入][此时可用的背包容量j]
    dp = [[0 for _1 in range(total + 1)] for _2 in range(item_num + 1)]  # which is : int dp[item_num+1][total+1] = {0}
    trace = [[[] for _1 in range(total + 1)] for _2 in range(item_num + 1)]  # 放入背包中的物品的最优组合的序号list
    for i in range(item_num):  # 第i+1次尝试放入第i个物品(物品序号从0起||显然，尝试次数从1起,即i+1)
        for j in range(total, -1, -1):  # form $total to $0, step=-1  # 第i+1次尝试放入时的现有背包可用容量
            (trace[i + 1][j], dp[i + 1][j]) = (trace[i][int(j - w[i])] + [i], dp[i][j - w[i]] + v[i]) \
                if j >= w[i] and dp[i][j - w[i]] + v[i] > dp[i][j] else (trace[i][j], dp[i][j])
            # which is:
            # if j >= w[i] and dp[i][j - w[i]] + v[i] > dp[i][j]:  # 第[i+1]次尝试放入时选择放入第[i]个物品
            #     dp[i + 1][j] = dp[i][j - w[i]] + v[i]  # 更新第i+1次尝试放入的推测值
            #     trace[i + 1][j] = trace[i][int(j - w[i])] + [i]
            # else:  # 跳过物品，拷贝"前[i]次尝试放入"的堆栈数据到[i+1]上, 事实上可以直接放弃拷贝过程节省程序开销
            #     dp[i + 1][j] = dp[i][j]
            #     trace[i + 1][j] = trace[i][j]
    return {
        "max_value": dp[item_num][total],
        "package_trace": trace[item_num][total]
    }

算法优化

A.空间优化

在上一小节中我们已经给出了动态转移方程和求解方法，该算法的时间复杂度和空间复杂度均为O(total*item_num)。
在空间复杂度上，我们可以进一步进行优化。回到其动态转移方程：

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[i+1]这个更高的维度似乎并没有用处，我们只是在dp[i]维度上拷贝数据到dp[i+1]：

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

这是因为，动态转移过程中推测dp[i+1][j]基于的是dp[i][j-w[i]]的值，只要保证推测dp[i+1][j]时，所基于的dp[i][j-w[i]]的值是上一个状态的值就行，之后哪怕这个值被洗掉也没关系。而此时，如果我们选择逆序更新，实际上在我们改变dp[~][低位]时，所基于它的dp[~][高位]已经得到了更新，即我们可以直接省略一个维度：

dp[j]=max{dp[j−wi]+vi,dp[j]}dp[j]=max\{dp[j-w_i]+v_i, dp[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
def solution_compress(data):
    """
    带空间压缩的 0-1 背包问题
    :param data: 数据集
    :return: 最优价值和放入背包的物品序号
    """
    total, w, v, answer = data.values()
    item_num = len(w)
    dp = [0 for _1 in range(total + 1)]  # which is : int dp[total+1] = {0}
    trace = [[] for _1 in range(total + 1)]
    for i in range(item_num):
        for j in range(total, -1, -1):  # 必需保证是从后往前更新dp[]
            # update trace[] before dp[]
            trace[j], dp[j] = (trace[int(j - w[i])] + [i], dp[j - w[i]] + v[i])\
                if j >= w[i] and dp[j - w[i]] + v[i] > dp[j] else (trace[j], dp[j])
            # which is :
            # if j >= w[i] and dp[j - w[i]] + v[i] > dp[j]:
            #     dp[j] = dp[j - w[i]] + v[i]
            #     trace[j] = trace[int(j - w[i])] + [i]
            # else:
            #     dp[j] = dp[j]  # 显然这里可以直接break以加快算法速度
            #     trace[j] = trace[j]
    return {
        "max_value": dp[total],
        "package_trace": trace[total]
    }

B.算法加速

在上一小节中我们压缩了空间，在代码solution_compress中其实可以看到：

1
2
3
4
5
6
if j >= w[i] and dp[j - w[i]] + v[i] > dp[j]:
    dp[j] = dp[j - w[i]] + v[i]
    trace[j] = trace[int(j - w[i])] + [i]
else:
    dp[j] = dp[j]  # 显然这里可以直接break以加快算法速度 即 if j < w[i] : break
    trace[j] = trace[j]

因此遍历所有可能的背包剩余空间是没有意义的，甚至会浪费大量的时间，改写上面的代码如下：(完整代码@码云)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solution_speedup(data):
    """
    带空间压缩和加速的 0-1 背包问题
    :param data: 数据集
    :return: 最优价值和放入背包的物品序号
    """
    total, w, v, answer = data.values()
    item_num = len(w)
    dp = [0 for _1 in range(total + 1)]
    trace = [[] for _1 in range(total + 1)]
    for i in range(item_num):
        # 修改动态过程中，修改下限 0 -> w[i]
        for j in range(total, w[i]-1, -1):  # form $total to $w[i], step=-1
            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])
            # which is :
            # if j >= w[i] and dp[j - w[i]] + v[i] > dp[j]:
            #     dp[j] = dp[j - w[i]] + v[i]
            #     trace[j] = trace[int(j - w[i])] + [i]
    return {
        "max_value": dp[total],
        "package_trace": trace[total]
    }

但这还是不够快，我们可以把下限进一步压缩：

max{total−∑t=iitem_numwt),w[i]}max\{total-\sum_{t=i}^{item\_num}w_t), w[i]\}

这是因为：背包总大小减去前几次可能放入的总重量(total-sum(w[i:]))与当前物品的重量相比(w[i])，前者称为“最大剩余重量容量”，当最大剩余重量容量大于当前物品的重量时，前者减去后者的差值部分，即多余的重量容量，并不会因为考虑要不要放入wiw_i而变得有所不同。实现代码如下：(完整代码@码云)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution_speedup_plus(data):
    """
    带空间压缩和进一步加速的 0-1 背包问题
    :param data: 数据集
    :return: 最优价值和放入背包的物品序号
    """
    total, w, v, answer = data.values()
    item_num = len(w)
    dp = [0 for _1 in range(total + 1)]
    trace = [[] for _1 in range(total + 1)]
    for i in range(item_num):
        lower = max(total-sum(w[i:]), w[i])  # 修正下限，进一步加速
        for j in range(total, lower-1, -1):
            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])
    return {
        "max_value": dp[total],
        "package_trace": trace[total]
    }

算法约束

恰好放满背包

现在，给原题目加上一个约束限制：要把背包恰好放满。

此处直接给出基于solution_speedup_plus给出修改后的代码：(完整代码@码云)

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
def solution_restrict(data, restrict=True):
    """
    带空间压缩和进一步加速的 0-1 背包问题(兼容约束解决方案)
    :param data: 数据集
    :param restrict: 是否进行装满约束
    :return: 最优价值和放入背包的物品序号
    """
    total, w, v, answer = data.values()
    item_num = len(w)
    specific = float("-inf") if restrict else 0  # 如果存在约束，指定所有背包容量为负无穷大
    # 只有初始状态装了0个物品且尚余容量为0的背包能够恰好被装满
    # 因为无论如何不放任何东西就是合法的解，而放了就表示必须将其占满——
    # 即上一个状态(初始时为放了0个物品的状态)背包满了(合法解)，则下一个状态才可能是满的
    # 如果找不到任何可行解，则dp[total]=negative infinite，即非法解
    dp = [specific for _1 in range(total + 1)]
    dp[0] = 0
    trace = [[] for _1 in range(total + 1)]
    for i in range(item_num):
        lower = max(total-sum(w[i:]), w[i])
        for j in range(total, lower-1, -1):
            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])
    return {
        "max_value": dp[total],
        "package_trace": trace[total]
    }

在该约束条件下修改了的部分只有这两行：

1
2
dp = [-∞ for _ in range(total + 1)]
dp[0] = 0

即把除了dp[0]以外的值初始化为负无穷大，dp[0]仍旧等于0。为什么这么做就能满足约束呢？

在动态过程中，当前一个状态的背包价值出现负无穷大时，显然dp[j] = dp[j-w[i]]+v[i]永不触发，除非dp[~]大于等于0(或者说为一个有效值)，也就是说放入了wiw_i之后，背包价值得到了提升但背包剩余容量仍为0，随着动态过程的推演，最终输出的可行解必然是由dp[0]演化得到的解，而此时仍旧保证了背包剩余容量为0，即背包容量被填满。

dp[i][j](或dp[j])有效的的意思是，在某个转移状态 ii 中，剩余 jj 容量的状态的价值dp[i][j]是大于0的，因为一个背包不可能出现负容量和负无穷大的价值。

  • 显然，要满足“装满约束”，有且只能有dp[0][0]=0有效且恰好装满(jj 等于0、包内价值等于0)，其它全部设为负无穷大即无效值。

完整代码测试

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

01-package.py测试结果：

1
2
3
4
5
function[solution] get result: {'max_value': 21, 'package_trace': [0, 2, 3, 5]} while repeat 5000 times, using time: 35.88(s)
function[solution_compress] get result: {'max_value': 21, 'package_trace': [0, 2, 3, 5]} while repeat 5000 times, using time: 26.72(s)
function[solution_speedup] get result: {'max_value': 21, 'package_trace': [0, 2, 3, 5]} while repeat 5000 times, using time: 19.12(s)
function[solution_speedup_plus] get result: {'max_value': 21, 'package_trace': [0, 2, 3, 5]} while repeat 5000 times, using time: 18.19(s)
function[solution_restrict] get result: {'max_value': 20, 'package_trace': [0, 1, 3]} while repeat 1 times, using time: 0.00(s)

> 点此下载代码

后续

算法:动态规划|背包问题②|完全背包问题的问题转化思路与优化(python实现)
  1. 1. 题目描述
  2. 2. 问题求解
    1. 2.1. A.动态过程
    2. 2.2. B.代码求解
  3. 3. 算法优化
    1. 3.1. A.空间优化
    2. 3.2. B.算法加速
  4. 4. 算法约束
    1. 4.1. 恰好放满背包
  5. 5. 完整代码测试
  6. 6. 后续