动态规划算法之0-1背包问题_0-1背包问题动态规划算法

 动态规划算法介绍
（1） 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
（2）动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解
（3）与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
（4）动态规划可以通过填表的方式来逐步推进，得到最优解

0-1背包问题的动态规划图解

（1）0-1背包问题描述：

有一个背包，容量为4，现有如下物品

（1.1）要求达到的目标为 装入背包中的物品的总价值最大，并且物品的总重量不超出背包的容量

（1.2）要求 装入的物品不能重复

（2）思路分析

利用动态规划来解决,每次遍历到的第 i 个物品，根据 weight[i] 与 value[i] 来确定是否需要将该物品放入背包中。即对于给定的 n个物品，设 weight[i]、value[i] 分别为第 i 个物品的重量与价值