背包问题

前言

在21年我第一次学习动态规划算法的时候，HQ学长安排的入门题目即是背包。直至前不久我只把背包当成一种有限的题目来看，未想还有如此讲究。

实际上，有很多问题可以规约为一个背包问题。

背包问题的三类

• 01背包：某物品选 or 不选；
• 完全背包：某物品无限多可选；
• 多重背包：某物品有n[i]件可选。

👇以下内容主要摘自：希望用一种规律搞定背包问题 - 组合总和 Ⅳ - 力扣（LeetCode） (leetcode-cn.com)

样题（LeetCode）

1. 组合问题：

1
2
3

377. 组合总和 Ⅳ
378. 目标和
379. 零钱兑换 II

2. True、False问题：

1
2

377. 单词拆分
378. 分割等和子集

3. 最大最小问题：

1
2

377. 一和零
378. 零钱兑换

公式一览

1. 组合问题公式

1

dp[i] += dp[i-num]

2. True、False问题公式

1

dp[i] = dp[i] or dp[i-num]

3. 最大最小问题公式

1
2

dp[i] = min(dp[i], dp[i-num]+1)
dp[i] = max(dp[i], dp[i-num]+1)

问题几步骤

1. 分析是否为背包问题。
2. 是以上三种背包问题中的哪一种。
3. 是0-1背包问题还是完全背包问题。也就是题目给的nums数组中的元素是否可以重复使用。
4. 如果是组合问题，是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法，不需要考虑顺序又有对应的解法。

背包问题的判定

背包问题具备的特征：给定一个target，target可以是数字也可以是字符串，再给定一个数组nums，nums中装的可能是数字，也可能是字符串，问：能否使用nums中的元素做各种排列组合得到target。

背包问题技巧：

1. 如果是0-1背包，即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序；

1
2

for num in nums:
    for i in range(target, nums-1, -1):

2. 如果是完全背包，即数组中的元素可重复使用，nums放在外循环，target在内循环。且内循环正序。

1
2

for num in nums:
    for i in range(nums, target+1):

3. 如果组合问题需考虑元素之间的顺序，需将target放在外循环，将nums放在内循环。

1
2

for i in range(1, target+1):
    for num in nums:

参考

希望用一种规律搞定背包问题 - 组合总和 Ⅳ - 力扣（LeetCode） (leetcode-cn.com)

【动态规划】01背包问题（通俗易懂，超基础讲解）_Yngz_Miao的博客-CSDN博客_01背包问题动态规划详解

动态规划：完全背包、多重背包_Allen_0526的博客-CSDN博客_完全背包

背包九讲（转载，实在不知道哪个是原创了） - _努力努力再努力x - 博客园 (cnblogs.com)