解题步骤
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
01背包注意事项
二维dp:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
一维dp:
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
二维dp遍历的时候,背包容量是从小到大,而一维dp遍历的时候,背包是从大到小。
为什么呢?
倒序遍历是为了保证物品i只被放入一次!。但如果一旦正序遍历了,那么物品0就会被重复加入多次!
举一个例子:物品0的重量weight[0] = 1,价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了,意味着物品0,被放入了两次,所以不能正序遍历。
为什么倒序遍历,就可以保证物品只放入一次呢?
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15
(dp数组已经都初始化为0)dp[1] = dp[1 - weight[0]] + value[0] = 15
所以从后往前循环,每次取得状态不会和之前取得状态重合,这样每种物品就只取一次了。
那么问题又来了,为什么二维dp数组遍历的时候不用倒序呢?
因为对于二维dp,dp[i][j]都是通过上一层即dp[i - 1][j]计算而来,本层的dp[i][j]并不会被覆盖!
背包问题分类
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F13d5f67b-84ef-4697-92f8-fac38e183453%2F0ee2db5b-13b6-43e9-8bee-bf4c1aae83b3%2FUntitled.png?table=block&id=ad5f99fa-7507-453d-84ce-e1a5259ad81d&t=ad5f99fa-7507-453d-84ce-e1a5259ad81d&width=1820&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F13d5f67b-84ef-4697-92f8-fac38e183453%2Fd76fe089-b067-46fb-bc37-f967c89efd40%2FUntitled.png?table=block&id=e588bada-5a2b-498f-8c56-807b20ff64e7&t=e588bada-5a2b-498f-8c56-807b20ff64e7&width=707.9861450195312&cache=v2)
从集合的角度理解DP数组
DP:
完全背包:
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Ff542023c-1ca2-4c8b-9f29-51f9ed07e8a9%2FUntitled.png?table=block&id=bd5ea245-57e6-4e3f-86a2-490165f493e3&t=bd5ea245-57e6-4e3f-86a2-490165f493e3&width=1889&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Ff21e9e13-1803-4d95-b12e-d2657f2fc4f2%2FUntitled.png?table=block&id=4a752e6a-70b3-4928-b69b-ac5a8af33488&t=4a752e6a-70b3-4928-b69b-ac5a8af33488&width=1374&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fbab95732-3239-4bff-9cfd-3e6370dd4f13%2FUntitled.png?table=block&id=b2b26f32-ee8e-4c66-a315-a745ccdb1e98&t=b2b26f32-ee8e-4c66-a315-a745ccdb1e98&width=1396&cache=v2)
上面的方程为0-1背包
下面的方程为完全背包
多重背包不能采用完全背包的方式优化
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F3bf31e91-c13d-43cf-9772-1f4744133ce7%2FUntitled.png?table=block&id=e81a98e3-9781-40db-b913-19a6e76e571a&t=e81a98e3-9781-40db-b913-19a6e76e571a&width=1536&cache=v2)