首先，我将简要介绍一些经典算法的大致含义。
算法(我只有一次机会，为了达到目的，其他的我什么都没有考虑回溯算法。 我有好几次机会，但不是有时达不到目的吗？ 动态规划算法：随时阅读档案文件，以最华丽的方式到达终点。接下来的几篇文章可能都会围绕dp来说，从白话和较多篇幅去解释dp算法的内在
因为简要说明动态规划求解最佳策略的原理，明显降低了时间的复杂性，提高了代码的执行效率。 但是，动态规划确实也很难学习，但如果知道了解决方案，很多动态规划问题也可以用同样的思路解决。
将会用实际的问题，更好的去去理解动态规划
0-1背包问题根据上次关于回溯的算法，我知道是采用递归的思想穷举所有解法，选出最优，然后解决问题还是这个问题。 针对不同重量、不可分割的单品组，选择放在背包里的，在满足最大重量限制的前提下，考虑一下最接近最大重量的方法。
首先，让我们用递归树来解释一下：
首先，假设每件物品的重量为22463，i表示决定将第几件物品放入背包，http://www.Sina.com /表示当前背包中物品的总重量，(例如，2、2表示决定是否将第二个物品放入背包，决定前背包的总重量为2。
从递归树可以清楚地看到，一些子问题的解决方案是cw的，重复。 如果重复的计算必然会造成性能的丢失可以的话，在计算之前先搜索一下，如果计算过的话，直接拿来使用的话，一定会提高的。
实际上，动态规划的想法与此大致相同，但让我们来看看动态规划的想法。
首先将整体解分为n个阶段，每个阶段保留之前的结果一个物品是否在包里。 无论是否放入，背包重量假设都会变化，但是这些不同的变化对应于递归树的节点3358www.Sina.com/，为了不使节点呈指数增加，基于该层次的节点http://www.Sina
首先决策states[n][w]，合并重复的节点N表示第n个，w表示背包能承受的最大质量。 第0个(从0开始计算物品的数组)物品的重量为2，放入的话为states[0][2]，否则为states[0][0]。 但是，由于最大重量w为9，所以上面两个表达式的结果都为true。 而且，在第一个中，重量也是2，其结果，在states[1][4]、states[1][2]、states[1][0]中，有两个公式3358www false表示0，true表示1，效果图如下所示。
然后用代码来表达：
这就是整个动态规划的思路，而且时间复杂度比回溯的n有了很大的改善，wn，n表示物品的个数，w表示可装载的总重量。
但是，为了解决所有情况，归档时还占用了空间。 那么，有没有减少空间消耗的方法？
实际上，可以将二维数组转换为一维数组。 在动态传输的过程中，可以依赖于这个一维数组来进行。 显示以下代码。
0-1背包问题的升级版将这些物品赋予价值概念，对背包最温暖的承诺如何在重量一定的时候增加价值呢？
首先，这个问题也可以用追溯的方法解决：
还是对上面的代码画递归树，和前面的想法一样，但是添加了新的值： value
我发现在很多情况下，重量相同但价值有差异。 这就是我们的主题目标，舍弃相对价值低的，保留相对价值高的，保留递归的思维方式，不考虑其他状态。
因此，我们将继续采用动态规划思想。
设置二维数组states[n][w 1]以记录每个层可以达到的不同状态，但这次使用int类型而不是xdddls类型来记录当前状态的最大价值。 并且，按照迄今为止的想法，在现阶段的基础上，导出后续的状态。
然后翻译成代码：
其实想法都和以前一样，但这里引入了第三个变量，即value。 和前面的例子大同小异，时间的复杂性也依然是wn。