01背包可以说是背包问题的基础也是核心，是最经典的动态规划问题之一，
通过01背包模型，我们可以以初步探讨动态规划的妙处所在，同时积累解决背包模型的方法。

下面的几点便是在01背包与相同模型的题当中能认识并学到的东西

• 寻找问题与子问题的等价条件

• 维度的确定以及初始化

• 定义状态转移方程

• 优化空间的条件

题目背景:有 N 件物品和一个容量是 V 的背包。
每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，
且总价值最大。

分析

从集合角度出发，所有的方案都能整成一个集合，利用集合可以让我们有助于动态规划为什么能怎么做，实际上状态转移方程所表示的是当前状态下的最优解。具体到该问题，最优解是在总体积不超过背包容量条件下，总价值最大。
抽象一下条件，总体积不超j的条件下，总价值最大，它与子问题是什么关系呢？实际上，{0…j} <= V，{0…j}都能看作是问题V的子问题。
那么什么样的问题能称子问题？如果问题代表一个集合，那么子问题就是子集。

• 选取了N件物品

• 选取了i <= N件物品

也能是这样

• 选择了N件物品背包容量不超过V的所有挑选方案

• 选择了i <= N件物品背包容量不超过j <= V的所有挑选方案

可以发现问题与子问题有相似之处，只是条件变量个数以及大小的不同!

动态规划的目的便是寻找规模更小的问题且与原问题相似，从而利用子问题来解决，核心思想就是分解原问题，从而更方便和快速解决问题。
那么动态规划核心找出子问题与问题的等价条件，才有所谓的状态转移以及方程。

01背包问题的等价条件是什么？

由题意可知，我们是要从所有物品中选取若干件物品，不妨设，当前状态是碰到第i件物品是否选取。

• 不选: 从前i件物品选取的所有获得的最大价值等价条件是从前i件物品选取且不选第i件(也即从前i-1件物品选取)中获得的最大价值。

• 选:也就变成了已知第i件物品选取得到了w的价值，怎么样能获得最大价值，同样的做法，我们可以从前i - 1件物品挑选方案中找到一个能获得最大价值的方案

问题的规模变小了! 可以发现动态规划类似递推式
$$ F(n) = F(n-1) + F(n-2), n > 2 $$
无需重复计算。而是利用了之前状态，而利用哪些状态，取决于当前问题与子问题有哪些等价条件，而等价条件要从条件变量进行推导

再分析

如果说状态转移方程大小取决于所有状态的数量，那么维度则取决于状态的种类或个数
前面我们貌似没考虑体积的限制条件)，类似于上面探讨过的从条件变量的大小确定等价条件，我们分析另一个条件变量体积实际上就是对上面的等价条件进行限制

设当前状态下背包容量为j
* 不选: 从前i件物品选取的且不体积超过j所有获得的最大价值等价条件是从前i件物品选取且不选第i件(也即从前i-1件物品选取)且体积不超过j中获得的最大价值。

• 选:也就变成了已知第i件物品选取得到了w的价值，怎么样能获得最大价值，同样的做法，我们可以从前i - 1件物品挑选且体积不超过j-v方案中找到一个能获得最大价值的方案

不难看出加入新的条件变量，对不加变量j集合中取了交集也即状态叠加，因此，状态转移方程维度取决选取条件变量的个数，二维背包费用就是01背包的扩充。

定义以及优化

由上面分析，不难写出状态转移方程

$$ F(i,j) = max(F(i - 1, j), F(i - 1, j - vi) + wi) $$

那么最优解即f(N,V)
其实我们能从定义的状态转移方程中发现并学到有用的东西，比如如何根据定义初始化，为什么空间能优化，对于利用方程能否判断某件物品是否被选，最优解方案总数，等等都是基于定义或是方程发现的。
下面是空间的优化，学习动态规划的空间优化是很有必要的，而初学时却不理解的时为什么对体积的循环为什么是逆序的，即for(j = m…0)
观察第一维的i，发现状态转移都是采用i - 1去推的，因此我们可以只保留i-1层的所有状态

$$ F(j) = max(F(j), F(j - vi) + wi) $$

还要注意一件事情的是若体积循环顺序没有逆序，会发生什么情况?
当到了第i层，那么所有f(j)都是第i-1层的状态
可能会用到F(j - vi)，更新第i层状态保存在了f(j)，但是从小到大循环，用到的F(j - vi)可能已经是第i层的状态了

正解:体积按m…0转移，保证了i状态都是由i-1状态推出的

结语

01背包问题中，从集合角度分析子问题与问题的等价条件，有利于对问题的理解，是确定了状态方程的定义的重要步骤，01背包中的空间的优化也是动态规划空间优化学习中相当重要的一步。
如何加深对01背包理解，我认为是多思考，多做题，才有收获
下面是对于01背包相关练习推荐
01背包问题
多维条件变量背包
等价条件理解1
等价条件理解2
综合(01背包+等价条件+多维条件+空间优化)