背包问题——是动态规划还是贪心算法？
这一篇我们先来详细说一说，什么是0-1背包问题？
当我们需要解决一个现实生活中的实际问题时，首先，能够对其进行正确地形式化定义是求解问题的前提。（都怪小迷糊当初语文没有学好
）
如果我们当前想不出好的解决办法怎么办，不如试试蛮力枚举法（反正小迷糊多的是
），说不定还可以找到新的灵感，千万不要放弃呀！
然后，检查体积约束，筛除掉超过背包体积（13）的商品组合。
最后，我们选取总价值最大的背包。
下面我们用计算机语言来描述上述求解过程，函数KnapsackSR(h,i,c)表示在第h个商品到第i个商品中，容量为c时的最优解。
下面来看看它的伪代码。
接下来，我们用之前学过的来分析蛮力枚举算法的时间复杂度。
下面是它的伪代码。
刻画最优解结构（如果一个问题的最优解包含其子问题的最优解，我们称此问题具有最优子结构的性质）；
自顶向下的递归定义最优解的值。
如果我们将每个子问题的最优解P[i,c]存在一个表中，观察子问题的依赖关系，可以发现P[i,c]由其左上方的子问题P[i-1,c-vi]和上方的子问题P[i-1,c]计算而得。
如果我们不用递归算法，则需要找到子问题的计算顺序（先求较小的子问题，然后是较大的子问题），你能填满这张表吗？
那我们就需要另一张表来记录这个决策过程，这个过程就是最优解的追踪。
最后，追踪最优解，即回溯的过程——倒序判断是否选择商品，根据选择结果，确定最优子问题。
刻画最优解结构（如果一个问题的最优解包含其子问题的最优解，我们称此问题具有最优子结构的性质）；
自顶向下的递归定义最优解的值；
采用自底向上的方法计算最优解的值；
最优方案追踪。
注
无论是带备忘的自顶向下法，还是自底向上法，这两种动态规划方法具有相同的渐近运行时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销，自底向上方法的时间复杂度函数通常具有更小的系数。
-
问题结构分析：给出问题表示，明确原始问题 递推关系建立：分析最优结构，构造递推公式
自底向上计算：确定计算顺序，依次求解问题
最优方案追踪：记录决策过程，输出最优方案
没错，动态规划和分治算法的主要区别就在于子问题的划分。
子问题 |
重复子问题 |
子问题求解 |
|
动态规划 |
互相重叠 |
只求解一次（保存在表格或备忘录中） |
既可以是带备忘的递归方法，也可以是自底向上的表格法 |
分治算法 |
互不相交 |
多次求解 |
递归 |