2023-08-20 12:37

关注

一种方法解决所有背包问题

QQ20230819-235704@2x.png

本文首发于微信公众号《前端和大数据》

背包问题是一种特定的最优化问题. 在业务和面试中都很常见. 这个问题的形式通常是：给定一组物品，每个物品都有相应的重量和价值，目标是在不超过背包容量限制的情况下，选择部分（或全部）物品，使总价值最大。

解决背包问题, 通常需要用动态规划的方法.

现实中的应用场景

在现实中有如下很多实际应用场景

物流与供应链：在决定要运送哪些货物时，可能需要考虑每个货物的价值和重量（或体积）来最大化装载价值。
资源分配：在有限的预算下，如何为多个项目分配资金以达到最大收益。
电力管理：在数据中心等环境中，如何根据设备功耗和计算效率分配电力，以获得最大的计算效果。
投资组合优化：在考虑投资组合时，投资者可能希望在风险和回报之间找到平衡。这可以视为一个背包问题，其中项的权重是风险，值是预期回报。
工作调度：在给定资源限制的情况下，如何安排任务以使利润最大化。
指标优化：在网络设计或其他工程领域，可能需要在满足一定约束条件下选择一组参数或元素，以优化某些性能指标。

背包问题的类型

根据对数量的限制背包问题有3种类型

0-1背包问题：每种物品只有一个，可以选择放入或不放入, 没有中间态。
完全背包问题：每种物品有无限个，可以任意选择数量放入。
多重背包问题：每种物品有限定数量，可以选择部分数量放入。

通用解决思路

背包问题也是动态规划问题, 因此可以采用动态规划的一般流程解决.

定义子问题：将原问题分解为更小的、更易于管理的部分。这些子问题通常是重复出现并且独立的。
构建DP表格/数组：创建一个表格或数组来存储每个子问题的答案。多数情况下，该表格/数组是从最简单的基础情况逐步构建起来的。
初始状态设定：确定并设置基础子问题的解。对于很多问题，这一步可能涉及到初始化DP表格/数组的边界值。
状态转移方程定义：找出一个公式或者方法，用于通过已知的子问题的解计算其他子问题的解。
代码实现：使用动态规划表格/数组求解原问题。这通常涉及到从表格/数组中读取或汇总信息。
定义 bad case

标准的背包问题

如下是一个标准的背包问题

有5个物品, 重量分别是  1kg, 1kg, 2kg, 10kg, 12kg 他们的价值分别是 1, 2, 2, 10, 4. 把他们装到容量为15kg 的背包中, 能装的最大金额是多少?

[[Pasted image 20230818163725.png]]

按通用解决思路分析:

定义子问题对于前 i 个物品, 当限重为 j 时的最大价值
构建 DP 表格横坐标为包的限重, 总坐标为前 i 个物品

   包的限重为j时
   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
0  0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0
1  0  1  1  1  1  1  1  1  1  1  1   1   1   1   1   1
2  0  2  3  3  3  3  3  3  3  3  3   3   3   3   3   3
3  0  2  3  4  5  5  5  5  5  5  5   5   5   5   5   5
4  0  2  3  4  5  5  5  5  5  5  10  12  13  14  15  15
5  0  2  3  4  5  5  5  5  5  5  10  12  13  14  15  15
前i个物品

定义状态转换方程每个物品有2种状态, 可以选择放入背包或不放入不放入第i 个物品时的价值 dp[i-1][j] 放入第 i 个物品时的价值为 dp[i-1][j-weight[i]]+value[i] 因此前 i 个物品, 限重为 j 时的最大值为

dp[i][j] = max(dp[i-1][j-weight[i]]+value[i], dp[i-1][j])

定义初始状态当 i = 0 时, 即未放入物品时, dp[0][x] = 0. 0<= x <= 包的最大限重 当 j = 0 时, 即包的限重为0时, 那么所有的价值也都是 0 . dp[x][0] = 0. 0<= x <= 物品数量
代码实现以下为 python 版本的实现


def knapsack(weight, value, capacity):
    goods_cnt = len(weight)
    dp = [[0 for _ in range(capacity + 1)]
          for _ in range(goods_cnt + 1)]

    for i in range(1, goods_cnt + 1):
        dp[i][0] = 0
        for j in range(1, capacity + 1):
            if weight[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j],
                               dp[i - 1][j - weight[i - 1]] + value[i - 1])

    return dp[goods_cnt][knapsack_capacity]

# 测试用例
1kg, 1kg, 2kg, 10kg, 12kg 他们的价值分别是 1, 2, 2, 10, 4. 把他们装到容量为15kg 的
weight, value, capacity = [1,1,2,10,12], [1,2,2,10,4], 15

knapsack(weight, value, capacity)

其他的背包问题都可以转为基于标准背包问题的形式

0-1背包(0-1 knapsack problem)

01背包是指每个物品可以选择放入或不放入背包, 只有这2种状态的情况. 标准背包也是一个01背包问题

分割等和子集

leetcode 416 题题目: 给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1, 5, 4, 7, 5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [4, 7] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

解析

与标准问题不同, 该题是求价值能否刚好等于固定值, 而非物品的最大价值. 该题可以转化为求一个数组中能否找到一个子集, 使该子集的合等于整个数组的一半.

转为标准背包问题对于示例1 , nums= [1, 5, 4, 7, 5], 可以转为如下问题有 4 个物品, 价值 value = [1, 5, 4, 7, 5], 物品重量 weight = [1, 5, 4, 7, 5] , 背包容量为 sum(value) / 2 = 11 求能否取 n 个物品, 使其装到背包中后的总价值为 11

解题步骤:

定义子问题. dp[i][j] 为前 i 个物品时, 装入容量为 j 的背包时, 总价值是否为target
构建 DP 表格

   0  1  2  3  4  5  6  7  8  9  10 11 x轴表示物品总重量 
0  T  F  F  F  F  F  F  F  F  F  F  F 
1  T  T  F  F  F  F  F  F  F  F  F  F
2  T  T  F  F  F  F  T  F  F  F  F  F
3  T  T  F  F  T  T  F  F  F  F  T  F
4  T  T  F  F  T  T  F  T  T  F  F  T
5  T  T  F  F  T  T  T  T  F  F  T  T
y轴表示前i个物品

定义状态转换方程与标准背包类似, 不过这里dp的值是布尔值, 表示价值是否刚好等于目标值

# i 表示前 i 个物品, j 表示背包的总重量
# dp[i][j] 表示取前 i 个物品装到容量为 j 的背包时, 总价值能否刚好等于 j
# 不装入物品 i 时, 结果为
dp[i-1][j]
# 装入物品 i 时, 结果为
dp[i-1][j-weight[i - 1]] + value[i - 1] == j 
# 由于 value 与 weight 的值相同. 因此上面的公式等价于下面的
dp[i-1][j-weight[i - 1]]
# 结合这2种情况, 得到下面的方程
dp[i][j] = dp[i-1][j-weight[i - 1]] or dp[i - 1][j]

定义初始状态根据定义可知当 j = 0 时, dp[i][0] = True; 0 =< i <= len(nums)
代码实现

 def canPartition(nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False

        target = int(total / 2)
        n = len(nums)

        # 用二维数组实现
        dp = [[False for _ in range(target + 1)] for _ in range(n + 1)]
        dp[0][0] = True
        for i in range(1, n + 1):
            dp[i][0] = True
            for j in range(1, target + 1):
                if nums[i - 1] > j:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j - nums[i - 1]]
        return dp[n][target]

完全背包 UKP (unbounded knapsack problem)

完全背包指每种物品不限制数量的情况. 如硬币问题

硬币兑换

参考 leetcode 322 题题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

解析

标准背包中的纵轴 i 表示前 i 个物品, 在完全背包中的物品数量不限, 因此 y轴不能表示前 i 个物品. 这种情况下, y轴的 i 可以定义为第 i 种物品.

转为标准背包问题:

对于示例1, coins=[1, 2, 5], amount = 11. 有一组物品, 重量 weight = [1, 2, 5] 价值 value=[1, 2, 5]. 背包容量 capacity = 11, 求装入背包的物品价值刚好等于11 时的最小物品数量

解题步骤:

定义子问题： dp[i][j]表示只用 [0:i] 硬币, 凑到金额 j 时的最小硬币数量.
构建DP表格/数组：

                    x 轴背包的容量,也等于硬币总价值
   0   1    2    3    4    5    6    7    8    9   10   11
0  0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf
1  0,  1,   2,   3,   4,   5,   6,   7,   8,   9,   10,  11
2  0,  1,   1,   2,   2,   3,   3,   4,   4,   5,   5,   6
3  0,  1,   1,   2,   2,   1,   2,   2,   3,   3,   2,   3
y轴当前硬币序号

初始状态设定: dp初始化时默认值都设置为 float('inf'), 表示无法凑成当 j = 0 时, dp[i][0] = 0
状态转移方程定义当不使用该硬币时, 最小数量为 i-1时的总数量, 即 dp[i-1][j]. 总金额小于硬币面值时, 也无法使用该硬币当使用该硬币时, 最小数量是总额小于该硬币面值时的数量 + 1, dp[i][j-value[i]] + 1 得到状态方程

j < coins[i - 1] 时; dp[i][j] = dp[i-1][j]
j >= coins[i - 1] 时, dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i - 1]] + 1)

代码实现：

def coin_change(coins, amount):
 dp = [[float('inf') for _ in range(amount + 1)] for _ in range(len(coins) + 1)]
 dp[0][0] = 0
 for i in range(1, len(coins) + 1):
  dp[i][0] = 0
  for j in range(1, amount + 1):
   coin = coins[i - 1]
   if coin > j:
    dp[i][j] = dp[i-1][j]
   else:
    dp[i][j] = min(dp[i-1][j-coin] + 1,
          dp[i-1][j], dp[i][j - coin] + 1)
    return dp[len(coins)][amount]

多重背包BKP (bounded knapsack problem)

每种物品有限定的数量. 求最大价值

盗窃最大价值

题目

一个盗贼，闯进了一个商场，准备偷窃一些物品。你有一个背包，容量为10千克。商场中有如下物品可供选择：
1. 键盘, 重量1千克, 总共有3台, 每个价值6美元。
2. 音响, 重量2千克, 总共有2个, 每个价值10美元。
3. 笔记本电脑, 重量3千克, 总共有1台, 价值12美元。
每种物品数量有限。目标是选择一部分物品放入背包中，使得背包中的物品总价值最大，同时不超过背包的容量。

问题：盗贼应该选择哪些物品，以及每种物品应该选择多少，才能在不超过背包容量的前提下，使得背包中的物品总价值最大？

解析该情况的特殊之处在于数量是有限的, 且大于等于 1 . 因此无法使用 01背包或完全背包的方式解决. 需要对01背包进行变形. 还是把 dp[i][j] 的值定义为前 i 个物品, 限重为 j 的背包时的最大价值但是在计算 dp[i][j] 时, 需要依次遍历可能的数量, 获取最大价值

定义子问题前 i 件物品放入容量为 j 的背包时的最大价值等于放入数量依次为 [0: counts[i]] 时的最大值
构建DP表格/数组按示例的问题. weights, values, counts = [1, 2, 3], [6, 10, 12], [3, 2, 1] 背包容量 capacity = 10

    0  1  2  3  4  5  6  7  8  9  10
0   0  0  0  0  0  0  0  0  0  0  0
1   0  6  12 18 18 18 18 18 18 18 18
2   0  6  12 18 22 28 32 38 38 38 38
3   0  6  12 18 22 28 32 38 40 44 50

初始状态设定当 i = 0 或 j = 0 时, dp[i][j] = 0
状态转移方程定义：令 dp[i][j] 表示前 i 件物品放入容量为 j 的背包时的最大价值令 k 表示第 i 个物品取的数量为 k j < weight[k] 时: dp[i][j] = dp[i - 1][j] j >= weight[k] 时, k 个物品的最大价值为 dp[i - 1][j - weights[i - 1] * k] + values[i - 1] * k. 则

for k in range(0, counts[i - 1]):
 dp[i][j] = max(dp[i][j], dp[i - 1][j - weights[i - 1] * k] + values[i - 1] * k)

代码实现：

def bkp(weights, values, counts, capacity):
    weights = [0] + weights  # 头部补 0, 方便计算
    values = [0] + values  # 头部补 0, 方便计算
    counts = [0] + counts  # 头部补 0, 方便计算

    dp = [[0 for _ in range(capacity + 1)] for _ in range(len(weights))]

    for i in range(1, len(weights)):
        for j in range(1, capacity + 1):
            for k in range(1, counts[i] + 1):
                if weights[i] * k > j:
                    dp[i][j] = max(dp[i-1][j], dp[i][j], dp[i][j - 1])
                else:
                    dp[i][j] = max(dp[i-1][j - weights[i] * k] +
                                   values[i] * k, dp[i][j])

    return dp[-1][-1]