05. 背包问题知识（五）

ITCharge大约 15 分钟

背包问题知识（五）

8. 背包问题变种

8.1 求恰好装满背包的最大价值

背包问题求恰好装满背包的最大价值：在给定背包重量 $W$ ，每件物品重量 $weight[i]$ ，物品间相互关系（分组、依赖等）的背包问题中，请问在恰好装满背包的情况下，能装入背包的最大价值总和是多少？

在背包问题中，有的题目不要求把背包装满，而有的题目要求恰好装满背包。

如果题目要求「恰好装满背包」，则我们可在原有状态定义、状态转移方程的基础上，在初始化时，令 $dp[0] = 0$ ，以及 $d[w] = -\infty, 1 \le w \le W$ 。这样就可以保证最终得到的 $dp[W]$ 为恰好装满背包的最大价值总和。

这是因为：初始化的 $dp$ 数组实际上就是在没有任何物品可以放入背包时的「合法状态」。

如果不要求恰好装满背包，那么：

任何载重上限下的背包，在不放入任何物品时，都有一个合法解，此时背包所含物品的最大价值为 $0$ ，即 $dp[w] = 0, 0 \le w \le W$ 。

而如果要求恰好装满背包，那么：

只有载重上限为 $0$ 的背包，在不放入物品时，能够恰好装满背包（有合法解），此时背包所含物品的最大价值为 $0$ ，即 $dp[0] = 0$ 。
其他载重上限下的背包，在放入物品的时，都不能恰好装满背包（都没有合法解），此时背包所含物品的最大价值属于未定义状态，值应为 $-\infty$ ，即 $dp[w] = 0, 0 \le w \le W$ 。

这样在进行状态转移时，我们可以通过判断 $dp[w]$ 与 $-\infty$ 的关系，来判断是否能恰好装满背包。

下面我们以「0-1 背包问题」求恰好装满背包的最大价值为例。

0-1 背包问题求恰好装满背包的最大价值：有 $n$ 种物品和一个最多能装重量为 $W$ 的背包，第 $i$ 种物品的重量为 $weight[i]$ ，价值为 $value[i]$ ，每件物品有且只有 $1$ 件。请问在恰好装满背包的情况下，能装入背包的最大价值总和是多少？

思路 1：动态规划 + 一维状态

划分阶段：按照当前背包的载重上限进行阶段划分。
定义状态：定义状态 $dp[w]$ 表示为：将物品装入一个最多能装重量为 $w$ 的背包中，恰好装满背包的情况下，能装入背包的最大价值总和。
状态转移方程： $dp[w] = dp[w] + dp[w - weight[i - 1]]$
初始条件：
1. 只有载重上限为 $0$ 的背包，在不放入物品时，能够恰好装满背包（有合法解），此时背包所含物品的最大价值为 $0$ ，即 $dp[0] = 0$ 。
2. 其他载重上限下的背包，在放入物品的时，都不能恰好装满背包（都没有合法解），此时背包所含物品的最大价值属于未定义状态，值应为 $-\infty$ ，即 $dp[w] = 0, 0 \le w \le W$ 。
最终结果：根据我们之前定义的状态， $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中的方案总数。则最终结果为 $dp[W]$ ，其中 $W$ 为背包的载重上限。

思路 1：代码

class Solution:
    # 0-1 背包问题 求恰好装满背包的最大价值
    def zeroOnePackJustFillUp(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [float('-inf') for _ in range(W + 1)]
        dp[0] = 0
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 逆序枚举背包装载重量（避免状态值错误）
            for w in range(W, weight[i - 1] - 1, -1):
                # dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
                dp[w] = max(dp[w], dp[w - weight[i - 1]] + value[i - 1])
        
        if dp[W] == float('-inf'):
            return -1
        return dp[W]

思路 1：算法复杂度

时间复杂度： $O(n \times W)$ ，其中 $n$ 为物品种类数量， $W$ 为背包的载重上限。
空间复杂度： $O(W)$ 。

8.2 求方案总数

背包问题求方案数：在给定背包重量 $W$ ，每件物品重量 $weight[i]$ ，物品间相互关系（分组、依赖等）的背包问题中，请问在总重量不超过背包载重上限的情况下，或者在总重量不超过某一指定重量的情况下，一共有多少种方案？

这种问题就是将原有状态转移方程中的「求最大值」变为「求和」即可。

下面我们以「0-1 背包问题」求方案总数为例。

0-1 背包问题求方案数：有 $n$ 件物品和有一个最多能装重量为 $W$ 的背包。第 $i$ 件物品的重量为 $weight[i]$ ，价值为 $value[i]$ ，每件物品有且只有 $1$ 件。
请问在总重量不超过背包载重上限的情况下，一共有多少种方案？

如果使用二维状态定义，可定义状态 $dp[i][w]$ 为：前 $i$ 件物品放入一个最多能装重量为 $w$ 的背包中的方案总数。则状态转移方程为： $dp[i][w] = dp[i - 1][w] + dp[i][w - weight[i - 1]]$ 。
如果使用一维状态定义，可定义状态 $dp[w]$ 表示为：将物品装入一个最多能装重量为 $w$ 的背包中的方案总数。则状态转移方程为： $dp[w] = dp[w] + dp[w - weight[i - 1]]$ 。

下面我们使用一维状态定义方式解决「0-1 背包问题求解方案数」问题。

思路 2：动态规划 + 一维状态

划分阶段：按照物品种类的序号、当前背包的载重上限进行阶段划分。
定义状态：定义状态 $dp[w]$ 表示为：将物品装入一个最多能装重量为 $w$ 的背包中的方案总数。
状态转移方程： $dp[w] = dp[w] + dp[w - weight[i - 1]]$
初始条件：如果背包载重上限为 $0$ ，则一共有 $1$ 种方案（什么也不装），即 $dp[0] = 1$ 。
最终结果：根据我们之前定义的状态， $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中的方案总数。则最终结果为 $dp[W]$ ，其中 $W$ 为背包的载重上限。

思路 2：代码

class Solution:
    # 0-1 背包问题求方案总数
    def zeroOnePackNumbers(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [0 for _ in range(W + 1)]
        dp[0] = 1
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 逆序枚举背包装载重量
            for w in range(W, weight[i - 1] - 1, -1):
                # dp[w] = 前 i - 1 件物品装入载重为 w 的背包中的方案数 + 前 i 件物品装入载重为 w - weight[i - 1] 的背包中，再装入第 i - 1 件物品的方案数
                dp[w] = dp[w] + dp[w - weight[i - 1]]
                
        return dp[W]

思路 2：复杂度分析

时间复杂度： $O(n \times W)$ ，其中 $n$ 为物品种类数量， $W$ 为背包的载重上限。
空间复杂度： $O(W)$ 。

8.3 求最优方案数

背包问题求最优方案数：在给定背包重量 $W$ ，每件物品重量 $weight[i]$ 、物品价值 $value[i]$ ，物品间相互关系（分组、依赖等）的背包问题中，请问在总重量不超过背包载重上限的情况下，使背包总价值最大的方案数是多少？

通过结合「求背包最大可得价值」和「求方案数」两个问题的思路，我们可以分别定义两个状态：

定义 $dp[i][w]$ 表示为：前 $i$ 种物品放入一个最多能装重量为 $w$ 的背包中，可获得的最大价值。
定义 $op[i][w]$ 表示为：前 $i$ 种物品放入一个最多能装重量为 $w$ 的背包中，使背包总价值最大的方案数。

下面我们以「0-1 背包问题」求最优方案数为例。

0-1 背包问题求最优方案数：有 $n$ 种物品和一个最多能装重量为 $W$ 的背包，第 $i$ 种物品的重量为 $weight[i]$ ，价值为 $value[i]$ ，每件物品有且只有 $1$ 件。请问在总重量不超过背包载重上限的情况下，使背包总价值最大的方案数是多少？

思路 3：动态规划

划分阶段：按照物品种类的序号、当前背包的载重上限进行阶段划分。
定义状态：
1. 定义 $dp[i][w]$ 表示为：前 $i$ 种物品放入一个最多能装重量为 $w$ 的背包中，可获得的最大价值。
2. 定义 $op[i][w]$ 表示为：前 $i$ 种物品放入一个最多能装重量为 $w$ 的背包中，使背包总价值最大的方案数。
状态转移方程：
1. 如果 $dp[i - 1][w] < dp[i - 1][w - weight[i - 1]] + value[i - 1]$ ，则说明选择第 $i - 1$ 件物品获得价值更高，此时方案数 $op[i][w]$ 是在 $op[i - 1][w - weight[i - 1]]$ 基础上添加了第 $i - 1$ 件物品，因此方案数不变，即： $op[i][w] = op[i - 1][w - weight[i - 1]]$ 。
2. 如果 $dp[i - 1][w] = dp[i - 1][w - weight[i - 1]] + value[i - 1]$ ，则说明选择与不选择第 $i - 1$ 件物品获得价格相等，此时方案数应为两者之和，即： $op[i][w] = op[i - 1][w] + op[i - 1][w - weight[i - 1]]$ 。
3. 如果 $dp[i - 1][w] > dp[i - 1][w - weight[i - 1]] + value[i - 1]$ ，则说明不选择第 $i - 1$ 件物品获得价值更高，此时方案数等于之前方案数，即： $op[i][w] = op[i - 1][w]$ 。
初始条件：如果背包载重上限为 $0$ ，则一共有 $1$ 种方案（什么也不装），即 $dp[0] = 1$ 。
最终结果：根据我们之前定义的状态， $op[i][w]$ 表示为：前 $i$ 种物品放入一个最多能装重量为 $w$ 的背包中，使背包总价值最大的方案数。则最终结果为 $op[size][W]$ ，其中 $size$ 为物品的种类数， $W$ 为背包的载重上限。

思路 3：代码

class Solution:
    # 0-1 背包问题求最优方案数 思路 1
    def zeroOnePackMaxProfitNumbers1(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
        op = [[1 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 件物品装不下
                if w < weight[i - 1]:
                    # dp[i][w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」
                    dp[i][w] = dp[i - 1][w]
                    op[i][w] = op[i - 1][w]
                else:
                    # 选择第 i - 1 件物品获得价值更高
                    if dp[i - 1][w] < dp[i - 1][w - weight[i - 1]] + value[i - 1]:
                        dp[i][w] = dp[i - 1][w - weight[i - 1]] + value[i - 1]
                        # 在之前方案基础上添加了第 i - 1 件物品，因此方案数量不变
                        op[i][w] = op[i - 1][w - weight[i - 1]]
                    # 两种方式获得价格相等
                    elif dp[i - 1][w] == dp[i - 1][w - weight[i - 1]] + value[i - 1]:
                        dp[i][w] = dp[i - 1][w]
                        # 方案数 = 不使用第 i - 1 件物品的方案数 + 使用第 i - 1 件物品的方案数
                        op[i][w] = op[i - 1][w] + op[i - 1][w - weight[i - 1]]
                    # 不选择第 i - 1 件物品获得价值最高
                    else:
                        dp[i][w] = dp[i - 1][w]
                        # 不选择第 i - 1 件物品，与之前方案数相等
                        op[i][w] = op[i - 1][w]
                        
        return op[size][W]

思路 3：复杂度分析

时间复杂度： $O(n \times W)$ ，其中 $n$ 为物品种类数量， $W$ 为背包的载重上限。
空间复杂度： $O(n \times W)$ 。

8.4 求具体方案

背包问题求具体方案：在给定背包重量 $W$ ，每件物品重量 $weight[i]$ 、物品价值 $value[i]$ ，物品间相互关系（分组、依赖等）的背包问题中，请问将哪些物品装入背包，可使这些物品的总重量不超过背包载重上限，且价值总和最大？

一般背包问题都是求解一个最优值，但是如果要输出该最优值的具体方案，除了 $dp[i][w]$ ，我们可以再定义一个数组 $path[i][w]$ 用于记录状态转移时，所取的状态是状态转移方程中的哪一项，从而确定选择的具体物品。

下面我们以「0-1 背包问题」求具体方案为例。

0-1 背包问题求具体方案：有 $n$ 种物品和一个最多能装重量为 $W$ 的背包，第 $i$ 种物品的重量为 $weight[i]$ ，价值为 $value[i]$ ，每件物品有且只有 $1$ 件。请问将哪些物品装入背包，可使这些物品的总重量不超过背包载重上限，且价值总和最大？

思路 4：动态规划 + 路径记录

0-1 背包问题的状态转移方程为： $dp[i][w] = max \lbrace dp[i - 1][w], \quad dp[i - 1][w - weight[i - 1]] + value[i - 1] \rbrace$

则我们可以再定义一个 $path[i][w]$ 用于记录状态转移时，所取的状态是状态转移方程中的哪一项。

如果 $path[i][w] = False$ ，说明：转移到 $dp[i][w]$ 时，选择了前一项 $dp[i - 1][w]$ ，并且具体方案中不包括第 $i - 1$ 件物品。
如果 $paht[i][w] = True$ ，说明：转移到 $dp[i][w]$ 时，选择了后一项 $dp[i - 1][w - weight[i - 1]] + value[i - 1]$ ，并且具体方案中包括第 $i - 1$ 件物品。

思路 4：代码

class Solution:    
    # 0-1 背包问题求具体方案
    def zeroOnePackPrintPath(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
        path = [[False 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 件物品装不下
                if w < weight[i - 1]:
                    # dp[i][w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」
                    dp[i][w] = dp[i - 1][w]
                    path[i][w] = False
                else:
                    # 选择第 i - 1 件物品获得价值更高
                    if dp[i - 1][w] < dp[i - 1][w - weight[i - 1]] + value[i - 1]:
                        dp[i][w] = dp[i - 1][w - weight[i - 1]] + value[i - 1]
                        # 取状态转移式第二项：在之前方案基础上添加了第 i - 1 件物品
                        path[i][w] = True
                    # 两种方式获得价格相等
                    elif dp[i - 1][w] == dp[i - 1][w - weight[i - 1]] + value[i - 1]:
                        dp[i][w] = dp[i - 1][w]
                        # 取状态转移式第二项：尽量使用第 i - 1 件物品
                        path[i][w] = True
                    # 不选择第 i - 1 件物品获得价值最高
                    else:
                        dp[i][w] = dp[i - 1][w]
                        # 取状态转移式第一项：不选择第 i - 1 件物品
                        path[i][w] = False
                        
        res = []
        i, w = size, W
        while i >= 1 and w >= 0:
            if path[i][w]:
                res.append(str(i - 1))
                w -= weight[i - 1]
            i -= 1
            
        return " ".join(res[::-1])

思路 4：复杂度分析

时间复杂度： $O(n \times W)$ ，其中 $n$ 为物品种类数量， $W$ 为背包的载重上限。
空间复杂度： $O(n \times W)$ 。

8.5 求字典序最小的具体方案

这里的「字典序最小」指的是序号为 $0 \sim size - 1$ 的物品选择方案排列出来之后的字典序最小。

我们仍以「0-1 背包问题」求字典序最小的具体方案为例。

为了使「字典序最小」。我们可以先将物品的序号进行反转，从 $0 \sim size - 1$ 变为 $size - 1 \sim 0$ ，然后在返回具体方案时，再根据 $i = size - 1$ 将序号变回来。

这是为了在选择物品时，尽可能的向后选择反转后序号大的物品（即原序号小的物品），从而保证原序号为 $0 \sim size - 1$ 的物品选择方案排列出来之后的字典序最小。

思路 5：代码

class Solution:
    # 0-1 背包问题求具体方案，要求最小序输出
    def zeroOnePackPrintPathMinOrder(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
        path = [[False for _ in range(W + 1)] for _ in range(size + 1)]
        
        weight.reverse()
        value.reverse()
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 枚举背包装载重量
            for w in range(W + 1):
                # 第 i - 1 件物品装不下
                if w < weight[i - 1]:
                    # dp[i][w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」
                    dp[i][w] = dp[i - 1][w]
                    path[i][w] = False
                else:
                    # 选择第 i - 1 件物品获得价值更高
                    if dp[i - 1][w] < dp[i - 1][w - weight[i - 1]] + value[i - 1]:
                        dp[i][w] = dp[i - 1][w - weight[i - 1]] + value[i - 1]
                        # 取状态转移式第二项：在之前方案基础上添加了第 i - 1 件物品
                        path[i][w] = True
                    # 两种方式获得价格相等
                    elif dp[i - 1][w] == dp[i - 1][w - weight[i - 1]] + value[i - 1]:
                        dp[i][w] = dp[i - 1][w]
                        # 取状态转移式第二项：尽量使用第 i - 1 件物品
                        path[i][w] = True
                    # 不选择第 i - 1 件物品获得价值最高
                    else:
                        dp[i][w] = dp[i - 1][w]
                        # 取状态转移式第一项：不选择第 i - 1 件物品
                        path[i][w] = False
                        
        res = []
        i, w = size, W
        while i >= 1 and w >= 0:
            if path[i][w]:
                res.append(str(size - i))
                w -= weight[i - 1]
            i -= 1
            
        return " ".join(res)

思路 5：复杂度分析

时间复杂度： $O(n \times W)$ ，其中 $n$ 为物品种类数量， $W$ 为背包的载重上限。
空间复杂度： $O(n \times W)$ 。

参考资料

【资料】背包九讲 - 崔添翼
【文章】背包 DP - OI Wiki
【文章】背包问题——“01背包”最优方案总数分析及实现 - wumuzi 的博客
【文章】背包问题——“完全背包”最优方案总数分析及实现 - wumuzi的博客
【文章】背包问题——“01背包”及“完全背包”装满背包的方案总数分析及实现 - wumuzi的博客