8. 背包问题变种

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  2. 定义状态：定义状态 dp[w]表示为：将物品装入一个最多能装重量为 w 的背包中，恰好装满背包的情况下，能装入背包的最大价值总和。

  3. 状态转移方程：dp[w]=dp[w]+dp[w−weight[i−1]]

  4. 初始条件：

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

  5. 最终结果：根据我们之前定义的状态， dp[w] 表示为：将物品装入最多能装重量为 w 的背包中的方案总数。则最终结果为 dp[W]，其中 W 为背包的载重上限。

思路 1：代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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×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：动态规划 + 一维状态

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

思路 2：代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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×W)，其中 n 为物品种类数量，W 为背包的载重上限。
  • 空间复杂度：O(W)。

8.3 求最优方案数

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

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

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

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

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

思路 3：动态规划

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

  2. 定义状态：

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

  3. 状态转移方程：

image-20240323123810071

  1. 初始条件：如果背包载重上限为 0，则一共有 1 种方案（什么也不装），即 dp[0]=1。

  2. 最终结果：根据我们之前定义的状态， op[i] [w] 表示为：前 i 种物品放入一个最多能装重量为 w 的背包中，使背包总价值最大的方案数。则最终结果为 op[size] [W]，其中 size 为物品的种类数，W 为背包的载重上限。

思路 3：代码

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
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×W)，其中 n 为物品种类数量，W 为背包的载重上限。
  • 空间复杂度：O(n×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：动态规划 + 路径记录

image-20240323124216090

思路 4：代码

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
35
36
37
38
39
40
41
42
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×W)，其中 n 为物品种类数量，W 为背包的载重上限。
  • 空间复杂度：O(n×W)。

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

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

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

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

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

思路 5：代码

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
35
36
37
38
39
40
41
42
43
44
45
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×W)，其中 n 为物品种类数量，W 为背包的载重上限。
  • 空间复杂度：O(n×W)。

快来参与讨论吧~

博客近期分类标签归档
项目软件开发札记人工智能Staller
社交友链
更多关于本站
本站由 卡卡龙 使用 Stellar 1.27.0 主题创建

本站访问量 次. 本文阅读量 次.

Stellar Copyright Licenses Hexo 备案 描述文字 描述文字