0-1背包问题
动规标准套路 get起来！！ 状态+选择
1. 明确 「状态」和「选择」
1）状态有两个：「背包的容量」和「可选择的物品」
- 如何才能描述一个问题局面？只要给定几个可选物品和一个背包的容量限制，就形成了一个背包问题，对不对？所以状态有两个，就是「背包的容量」和「可选择的物品」。
2）选择：「装进背包」或者「不装进背包」
3）套框架
2. 明确dp数组的含义
dp数组是什么？其实就是描述问题局面的一个数组。换句话说，我们刚才明确问题有什么「状态」，现在需要用dp数组把状态表示出来
- 首先看看刚才找到的「状态」，有两个，也就是说我们需要一个二维dp数组，一维表示可选择的物品，一维表示背包的容量。
- dp[i][w]的定义：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]。
根据这个定义，我们想求的最终答案就是dp[N][W]。base case 就是dp[0][..] = dp[..][0] = 0，因为没有物品或者背包没有空间的时候，能装的最大价值就是 0。
3.根据「选择」，状态转移
简单说就是，上面伪码中「把物品i装进背包」和「不把物品i装进背包」怎么用代码体现出来呢？
重申dp数组dp[i][w]含义：对于前i个物品，当前背包的容量为w时，这时可以装下的最大价值是dp[i][w]。
- 如果你没有把这第i个物品装入背包，那么很显然，最大价值dp[i][w]应该等于dp[i-1][w]。你不装嘛，那就继承之前的结果。
如果你把这第i个物品装入了背包，那么dp[i][w]应该等于dp[i-1][w-wt[i-1]] + val[i-1]。
4. 边界情况
w - wt[i-1]可能小于 0 导致数组索引越界
子集背包问题
那么对于这个问题，我们可以先对集合求和，得出sum，把问题转化为背包问题：
给一个可装载重量为sum/2的背包和N个物品，每个物品的重量为nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满？
动规解题框架
第一步要明确两点，「状态」和「选择」。
第二步要明确dp数组的定义。
第三步，根据「选择」，思考状态转移的逻辑。
最后一步，把伪码翻译成代码，处理一些边界情况。
进行状态压缩
dp[i][j]都是通过上一行dp[i-1][..]转移过来的，之前的数据都不会再用了 —— 将二维dp数组压缩为一维
- 注意：j应该从后往前反向遍历，因为每个物品（即数字）只能用一次，以免之前的结果影响其他的结果
完全背包问题
- 这个问题和我们前面讲过的两个背包问题，有一个最大的区别就是，每个物品的数量是无限的，这也就是传说中的「完全背包问题」，没啥高大上的，无非就是状态转移方程有一点变化而已。
解题思路
- 状态 选择
- dp数组dp[i][j]的定义如下：若只使用前i个物品，当背包容量为j时，有dp[i][j]种方法可以装满背包。
- 根据选择，思考状态转移的逻辑
- 如果你不把这第i个物品装入背包，也就是说你不使用coins[i]这个面值的硬币，那么凑出面额j的方法数dp[i][j]应该等于dp[i-1][j]，继承之前的结果。
- 如果你把这第i个物品装入了背包，也就是说你使用coins[i]这个面值的硬币，那么dp[i][j]应该等于dp[i][j-coins[i-1]]。
综上两种选择，而我们想求的dp[i][j]是「共有多少种凑法」，所以dp[i][j]的值是以上两种选择结果之和：
- 伪码翻译成代码，处理一些边界情况。
- 压缩状态
若有收获，就点个赞吧
0 人点赞
