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

QQ20230819-235704@2x.png

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

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

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

现实中的应用场景

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

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

背包问题的类型

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

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

通用解决思路

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

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

标准的背包问题

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

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

[[Pasted image 20230818163725.png]]

按通用解决思路分析:

  1. 定义子问题 对于前 i 个物品, 当限重为 j 时的最大价值
  2. 构建 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  15i个物品
  1. 定义状态转换方程 每个物品有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])
  1. 定义初始状态 当 i = 0 时, 即未放入物品时, dp[0][x] = 0. 0<= x <= 包的最大限重 当 j = 0 时, 即包的限重为0时, 那么所有的价值也都是 0 . dp[x][0] = 0. 0<= x <= 物品数量
  2. 代码实现 以下为 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

解题步骤:

  1. 定义子问题. dp[i][j] 为前 i 个物品时, 装入容量为 j 的背包时, 总价值是否为target
  2. 构建 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个物品
  1. 定义状态转换方程 与标准背包类似, 不过这里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]
  1. 定义初始状态 根据定义可知 当 j = 0 时, dp[i][0] = True; 0 =< i <= len(nums)
  2. 代码实现
 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 时的最小物品数量

解题步骤:

  1. 定义子问题: dp[i][j]表示只用 [0:i] 硬币, 凑到金额 j 时的最小硬币数量.
  2. 构建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轴当前硬币序号
  1. 初始状态设定: dp初始化时默认值都设置为 float('inf'), 表示无法凑成 当 j = 0 时, dp[i][0] = 0
  2. 状态转移方程定义 当不使用该硬币时, 最小数量为 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)
  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] 时, 需要依次遍历可能的数量, 获取最大价值

  1. 定义子问题 前 i 件物品放入容量为 j 的背包时的最大价值等于放入数量依次为 [0: counts[i]] 时的最大值
  2. 构建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
  1. 初始状态设定 当 i = 0 或 j = 0 时, dp[i][j] = 0
  2. 状态转移方程定义: 令 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)
  1. 代码实现:
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]

总结

从物品数量限制的维度背包问题可以分为本文的3种情况, 都可以转为标准的背包问题.

但是初次之外还有其他背包类型的问题, 如多维背包, 即物品有多个维度, 背包有多个维度限制, 如需要同时满足体积和重量. 但是解决的步骤类似, 能列出 DP 表格之后, 通常可以找到规律. 并得到动态转移方程

本文使用 markdown.com.cn 排版

全部评论

相关推荐

没有offer的呆呆:薪资有的时候也能说明一些问题,太少了活不活得下去是一方面,感觉学习也有限
点赞 评论 收藏
分享
04-21 11:22
已编辑
中华女子学院 UE4
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务