引入
总体思路
此类问题一般是寻找最优解，但由于最终的最优解取决于前面一系列的决策，局部最优不一定能导出整体最优，所以贪心的思想对此种问题束手无策。所以需要从最简单的小问题开始，逐步扩展，最终扩展到我们需要的地方为止。这里的扩展就是决策，就是状态转移。根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出问题的最优解以及解组成，然后编写代码实现。
动态规划的原理
动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。
最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。
01背包
问题描述
有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
算法思想
在解决问题之前，为描述方便，首先定义一些变量：Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积，定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值，同时背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选）。
1、建立模型，即求max(V1X1+V2X2+…+VnXn)；
2、寻找约束条件，W1X1+W2X2+…+WnXn<capacity；
3、寻找递推关系式，面对当前商品有两种可能性：
（1）包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
（2）还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。
其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)；
由此可以得出递推关系式：
- j<w(i) V(i,j)=V(i-1,j)
- j>=w(i) V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝
这里需要解释一下，为什么能装的情况下，需要这样求解（这才是本问题的关键所在！）：
可以这么理解，如果要到达V(i,j)这一个状态有几种方式？
肯定是两种，第一种是第i件商品没有装进去，第二种是第i件商品装进去了。没有装进去很好理解，就是V(i-1,j)；装进去了怎么理解呢？如果装进去第i件商品，那么装入之前是什么状态，肯定是V(i-1,j-w(i))。由于最优性原理，V(i-1,j-w(i))就是前面决策造成的一种状态，后面的决策就要构成最优策略。两种情况进行比较，得出最优。
举个例子：
物品数量：4；背包容量：8
| i（物品编号） | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| w（体积） | 2 | 3 | 4 | 5 |
| v（价值） | 3 | 4 | 5 | 6 |
规划完的表格如下：
| i/j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 2 | 0 | 0 | 3 | 4 | 4 | 7 | 7 | 7 | 7 |
| 3 | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 9 |
| 4 | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 10 |
参考链接：【动态规划】01背包问题（通俗易懂，超基础讲解）_Yngz_Miao的博客-CSDN博客_动态规划解决01背包问题
最优解回溯
通过上面的方法可以求出背包问题的最优解，但还不知道这个最优解由哪些商品组成，故要根据最优解回溯找出解的组成，根据填表的原理可以有如下的寻解方式：
- V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，则回到V(i-1,j)；
- V(i,j)=V(i-1,j-w(i))+v(i)时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到V(i-1,j-w(i))；
一直遍历到i＝0结束为止，所有解的组成都会找到。
就拿上面的例子来说吧：
- 最优解为V(4,8)=10，而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10，所以第4件商品被选中，并且回到V(3,8-w(4))=V(3,3)；
- 有V(3,3)=V(2,3)=4，所以第3件商品没被选择，回到V(2,3)；
- 而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4，所以第2件商品被选中，并且回到V(1,3-w(2))=V(1,0)；
- 有V(1,0)=V(0,0)=0，所以第1件商品没被选择。
代码实现
输入格式：
第一行两个整数n，m表示物品数量及背包容量
接下来n行每行两个整数wi和vi，分别表示第i个物品的体积和价值
要求输出一个整数表示最大价值总和
样例输入：
4 8
2 3
3 4
4 5
5 6
样例输出：
10
c++实现：
|
空间优化
两重for循环是跑不掉的，也就是时间复杂度已经没办法优化了。不过空间复杂度还有极大的优化空间。
观察下面01背包的核心代码：
for (int i = 1; i <= n; i++) |
我们可以发现dp这个二维数组自始至终我们只用到了第i行和第i-1行。所以有一种朴素的想法就是dp可以压缩至两行，状态转移需要用到的空间只要在这两行之间反复横跳就行。
不过，这里我们要说的是可以优化到一维数组。再回到代码，我们可以发现j<w[i]时，我们只是把dp[i-1][j]的数据照搬了过来，其实并没有什么操作，如果用一维数组来刻画的话就是：现在这个一维数组里存的相当于是i-1行的数据，然后我们要转变为第i行还是存在这个数组里，j<w[i]时就相当于保留原数据。
再看else情况下，由于i-1行的数据也在这个一维数组里，所以我们可以直接删去i那一维，写成这样：
dp[j] = max(dp[j], dp[j - w[i]] + v[i]); |
有一点需要注意，dp[j-w[i]]需要用到数组里前面的数据，如果我们从前往后遍历的话，显然前面的数据被更新后才被后面使用，而我们需要的原数据就被覆盖没了，这不符合我们初衷，所以我们需要从后往前遍历。
优化后的核心代码如下：
for (int i = 1; i <= n; i++) |
我们再仔细分析一下这个代码，j>=w[i]时才需要操作，j<w[i]时不需要操作。j表示的是背包容量，当j过小时，对于第i件物品来说肯定是放不下的，根本没有我们选择放不放的余地。而且j遍历到0，对于dp[j - w[i]]是会发生越界的。所以我们完全可以直接遍历到w[i]，并且由于是从大到小遍历，j肯定不小于w[i]，那个if判断也可以拿掉。
最终优化版核心代码如下：
for (int i = 1; i <= n; i++) |
空间优化后的01背包是没办法进行最优解回溯的，因为历史数据我们都没有保留。所以，如果要进行最优解回溯的话，还是需要用二维数组来保存数据。
优化后完整版代码：
|
