背包问题

问题描述：给定N个物品和一个容量有限为V的背包，每个物品有两种属性：v[i]（该物品的体积）和 w[i]（该物品的价值，即权重），求解在不超过背包最大容量的情况下，能装下物品的最大价值是多少。

背包种类

1、01背包：每件物品只有一个（即每件物品要么装，要么不装，只有两种状态，故称01背包）
2、完全背包：每件物品有无限个
3、多重背包：每种物品有是s[i]个（不同物品的个数可能不同）
4、分组背包：物品被分为N组，每组有若干种，每组最多只能取一个物品
…………

一般思维方式

对于DP的一般思维方式可以用集合的角度来理解（下面以背包问题为例）
DP有两点要素：
（1）状态表示f[i][j]：
每一个状态就是一个集合，背包问题中每个集合f[i][j]表示的就是用容量为j的背包装前i个物品的最大价值。
不同问题下，集合的属性不同。背包问题中是最大价值，属性也可能是方式总数、元素数量等
（2）状态计算：
关键在于对（1）中集合的划分，做到不重不漏。

1、01背包

01背包的集合含义和状态转移方程：
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])
f[i][j]含义：容量为j的背包装前i个物品的最大价值
用滚动数组优化为一维：
f[j] = max(f[j], f[j - v[i]] + w[i])
此时遍历顺序：最外层遍历物品内层遍历背包容量。背包容量从大到小

下面给出LeetCode上01背包应用的几道典型例题以及关键思路也就是集合的含义和属性。
（1）纯粹的01背包：在背包容量下能装的最大价值
（2）416. 分割等和子集：根据题意得出背包大小sum / 2，求解背包能否正好被装满，能返回TRUE，不能返回FALSE
（3）1049. 最后一块石头的重量 II：根据题意得出背包大小sum / 2，求背包内能装下的最大重量
（4）494. 目标和：根据题意得到背包容量，求有多少中方式能把背包装满。
（5）474. 一和零：根据题意可知这是一个物品重量有两个维度的01背包，求背包容量下的最大重量
上述几道例题都是01背包在不同层面上的应用，由此可以总结归纳出01背包的特点：
1、「从序列中选择子序列使得和接近target」系列的题目，且序列中每个元素均最多使用一次，即只有用与不用两种状态，可以转换为01背包。
2、背包属性不能局限于重量，元素和等方向，也可以为装满背包的方式等。不同属性需考虑不同的状态转移方程和初始化。
如，单纯的重量，元素和：f[j] = max(f[j], f[j - v[i]] + w[i])，初始化：f[0] = 0
装满背包的方式：f[j] += f[j - v[i]]，初始化：f[0] = 1
对于初始化，可以考虑特殊情况代入，或者根据状态转移方程手搓几种情况得出。

2、完全背包

完全背包的集合含义和状态转移方程：
f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])
f[i][j]含义：容量为j的背包装前i个物品的最大价值
用滚动数组优化为一维：
f[j] = max(f[j], f[j - v[i]] + w[i])
此时遍历顺序：最外层遍历物品内层遍历背包容量，背包容量从小到大（或者最外层遍历背包容量内层遍历物品，但此时需要判断当前物品体积是否小于背包容量）

下面给出LeetCode上完全背包应用的几道典型例题以及关键思路。
（1）518. 零钱兑换 II：根据题意，总金额->背包最大容量，每一种面额的硬币有无限个->物品个数无限，所以这是一个完全背包，求装满背包的方式（组合数）
（2）377. 组合总和 Ⅳ：根据题意，求装满背包的方式（排列数）
由上述两个问题可以归纳出完全背包求组合数/排列数的一般思路：
所谓组合数，指元素位置不同的序列视为相同组合；排列数，指元素位置不同的序列视为不同组合。
求组合数，遍历顺序：先遍历物品再遍历背包容量
求排列数，遍历顺序：先遍历背包容量再遍历物品
状态转移方程均为：f[j] += f[j - v[i]]，初始化：f[0] = 1
可以手动模拟一下两种不同遍历顺序所得到的不同结果

未完待续

希望大家在刷题时能通过不同题目总结归纳出相同点和不同点，具体问题具体分析，关注细节。理解不同遍历方式，不同初始化的具体含义。相信大家一定能有所收货！