常见的背包问题

image.png

0-1背包
背景:有N件物品和⼀个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能⽤⼀次，求解将哪些物品装⼊背包⾥物品价值总和最⼤。

含义:dp[i][j]的含义：从下标为[0-i]的物品⾥任意取，放进容量为j的背包，价值总和最⼤是多少
两种选择
（1）不选:则dp[i][j]=dp[i - 1][j]
(2) 选:则 dp[i][j]=dap[i-1][j-weight[i]] + value[i];

所以最终的递归式为:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

优化
使用一维数组优化

对应的题目
分割等和⼦集
最后⼀块⽯头的重量 II

---

常见的背包问题有
1、组合问题。2、True、False问题。3、最大最小问题。

1、组合问题： 377. 组合总和 Ⅳ 494. 目标和 518. 零钱兑换 II

2、True、False问题： 139. 单词拆分 416. 分割等和子集

3、最大最小问题： 474. 一和零 322. 零钱兑换

---

组合问题公式

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

True、False问题公式

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

最大最小问题公式

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在内循环，且内循环倒序；

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

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

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

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

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