背包问题（Knapsack Problem）是指给定一个容量固定为W的背包和一组数量为n的物品，每个物品的重量为wi，价值为vi，要求从物品中选择若干放入背包，使总物品重量不超过背包容量，并且使价值最大。这是动态规划的一类非常典型的问题。
背包问题如果每种物品数量只有一个，那么每个物品只有两种状态『放入背包』和『不放入背包』，这个一般称作0-1背包问题；如果每种物品的数量无限又称完全背包。
物品可分割
这类背包问题最简单，它是说有n种物品，每种物品的总重是wi，价值是vi，每种物品可分割为更小的部分，求不超过背包总容量W，使放入背包的价值最大。
因为物品可分割，那么要想装满背包价值最大，就优先选择单位容积价值最大的物品，可以计算每种物品的价值容积比，然后从大到小排序，优先往背包里面装价值容积比大的物品，直到背包装满为止。这其实是贪心算法。
这个问题是有实际例子，比如往一个盒子里面装糖果，不同糖果价格不同，想要让盒子最贵，就优先往里面塞最贵的糖果。
可以看贪心算法的文章，里面有更详细的讨论。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 1710. 卡车上的最大单元数 | 题解 | |
| 题解 | ||
| 题解 | ||
| 题解 |
0-1背包问题
这是背包问题的基础，只有完全理解 了这类问题后，才能对其他背包问题有更好的理解。
0-1背包问题的特点是每种物品只有一个，对于每种物品的选择是放入背包，或者不放入。0-1背包问题与子集的问题一样的，从一堆物品中选择若干，其实就相当于对于一个集合选择子集，从回溯算法的一些实例中，可以得到一个暴力解法，可以用二进制枚举的方法，找出所有的子集，然后计算每个子集的总价值，最后取最大值即可。从子集问题可知，这样做的时间复杂度可达到O(2n)，非常的高。可以用动态规划来降低到O(n2)。
背包问题要采用子问题的思路，对于物品数量为n，背包容量为W，来说一个子问题是i个物品和容量为j，其中0<=i<n，0<=j<=W。那么，背包问题的状态转移方程就是f(i,j) = max{f(i-1,j), f(i-1, j-weight[i])+value[i])}，意即当前物品i要么不放入背包，那总价值就是背包之前的状态f(i-1,j)，或者放入，但要想把物品i放进去，必须要保证有足够的空间装下它，所以是f(i-1,j-weight[i])再加上当前物品的价值value[i]，这两者取最大值就是，到当前物品i，容易为j时的最大价值。当尝试完所有的物品和所有的容量后，最后f(n,W)就是整个问题的解。
背包问题的时间复杂度是O(n2)，因为你要遍历所有的物品和所有的容积，基本没有优化空间了，因为有两个参数，所以空间复杂度也是O(n2)，因为要用矩阵来存储所有的状态，更进一步可以用一维数组来缓存状态，从而把空间复杂度降低到O(n)。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 416. 分割等和子集 | 题解 | |
| 494. 目标和 | 题解 | |
| 题解 |
完全背包问题
完全背包与0-1背包的区别就在于每种物品i的数量是无限的，你想选多少就选多少。那么在选择的时候可以假设选择物品i的数量为k，显然k=1时就是0-1背包问题。 可以基于0-1背包进行拓展，来解决完全背包。依旧是取状态转移方向为f(i,j)为选择到物品i，容积为j时的背包最大价值，当到物品i时，可选0个，也可以选1个，也可以选k个，所以状态转移方程是f(i,j) = max{f(i-1, j-k*weight[i]) + k * values[i]}，其中i的取值是所有的物品0<=i<n，j是所有的容积0<=j<=W，而k是物品i的可选数量0<=k<j/weight[i]，也就是说当前物品最多能选择的数量就是当前容积的限制j/weight[i]。 时间复杂度会上升到O(n3)，空间复杂度可以从O(n2)优化到O(n)。
还可以换个思路，定义f(i)为背包容量为i时所能取得的最大价值，那么f(W)是问题的解。每种物品的数量是无限的，但也有范围，每种物品的最大数量显然是背包的最大容量，也就是说每种物品的数量上限是c[i] = W/w[i]。如何能得到f(i)呢？可以把每种物品都往里面放一个去尝试，比如把第j个物品放进背包，那么这时f(i) = f(i-w[j]) + v[j]，因为不知道要放哪一个，所以应该把所有的物品都尝试一遍，然后取最大值，也即是f(i) = max{f(i-w[j]) + v[j], when i-w[j]>=0}，这里j的取值范围是所有物品数量i-w[j]>=0是要保证背包还装得下，如果某个物品太大了装不下，超过了背包的容量限制，那也不能选择它。为了找到最后的解背包容量i要从0到W。这样时间复杂度就降低到O(n2)了。
典型题目
| 题目 | 题解 | 说明 |
|---|---|---|
| 279. 完全平方数 | 题解 | |
| 322. 零钱兑换 | 题解 | |
| 377. 组合总和 Ⅳ | 题解 | |
| 518. 零钱兑换 II | 题解 | |
| 题解 | ||
| 题解 |