动态规划算法介绍
（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 个物品的重量与价值，m 为背包的容量。再令 v[i][j] 表示在前 i 个物品中进行组合后装入容量为 j 的背包中的最大价值。则有下面的结果：
(2.1) v[0][i] = v[i][0]=0; // 表示 填入表 第一行和第一列都是 0
(2.2) 当 weight[i] > j 时，v[i][j] = v[i-1][j]; // 当准备加入的新增的商品的重量大于当前背包的容量时，就直接使用上一个单元格的装入策略
(2.3) 当 j >= weight[i-1] 时： v[i][j]=max{v[i-1][j], value[i] + v[i-1][j-weight[i]]} // 当准备加入的新增的商品的重量小于或者等于当前背包的容量时,使用的装入策略，各部分说明如下
v[i-1][j]： 就是上一个单元格的装入的最大价值
value[i] : 表示当前商品的价值
v[i-1][j-weight[i]] ： 装入前 i-1 个商品，到剩余背包容量 j-weight[i] 的最大价值
当 j >= weight[i] 时： v[i][j] = max{v[i-1][j], value[i]+v[i-1][j-weight[i]]} ;
（3）如下填表方式，逐步推导，得到最优解
代码实现
package com.zzb.algorithm.dynamic;
/**
* 动态规划算法
* 应用实例：0-1背包问题（限制每个物品要么拿（1个），要么不拿（0个））
*/
public class KnapsackProblem {
public static void main(String[] args) {
// 每个物品的重量
int[] weight = {1, 2, 4};
// 每个物品的价值
int[] value = {40, 30, 10};
// 背包的容量
int m = 4;
// 物品的个数
int n = value.length;
// v[i][j] 表示在前i个物品中进行组合后装入容量为j的背包中的最大价值
int[][] v = new int[n+1][m+1];
// 记录放入物品的情况
int[][] path = new int[n+1][m+1];
// 二维数组 int[][] v 的第一行与第一列的初始化
// 可以不处理，默认就是0
for(int i = 0; i < v[0].length; i++) {
v[0][i] = 0;
}
for(int i = 0; i < v.length; i++) {
v[i][0] = 0;
}
// 实现 0-1背包 中物品的最大值
// i 可理解为：第i个物品（行代表具有重量与价值的不用物品）
// j 可理解为：背包的不同容量（列代表不同容量的背包）
// v[i][j] 表示在前i个物品中进行组合后装入容量为j的背包中的最大价值
for(int i = 1; i < v.length; i++) { // 循环取出每一个物品
for(int j = 1; j < v[0].length; j++) { // 前i个物品在不用容量j的背包下的最大价值
// weight[i-1] value[i-1] 解释：i的初始值为1（i= 1），代表第一个物品，但是在weight[]中
// 第一个物品的下标索引为0，索引要 i - 1 指向第一个物品
if(weight[i-1] > j) { // 第i个物品的重量大于当前背包的容量j
v[i][j] = v[i-1][j];
} else {
if(v[i-1][j] < value[i-1] + v[i-1][j-weight[i-1]]) {
v[i][j] = value[i-1] + v[i-1][j-weight[i-1]];
// 记录第i个物品放入背包的情况
path[i][j] = 1;
} else {
v[i][j] = v[i-1][j];
}
}
}
}
// 不用容量的背包中物品的最大价值
for(int i =0; i < v.length; i++) {
for(int j = 0; j < v[i].length; j++) {
System.out.print(v[i][j] + "\t");
}
System.out.println();
}
/*0 0 0 0 0
0 40 40 40 40
0 40 40 70 70
0 40 40 70 70*/
System.out.println("============================");
for(int i = 0; i < path.length; i++) {
for(int j = 0; j < path[i].length; j++) {
if(path[i][j] == 1) {
System.out.println("第 " + i + " 个物品放入了背包");
}
}
}
/*第 1 个物品放入了背包
第 1 个物品放入了背包
第 1 个物品放入了背包
第 1 个物品放入了背包
第 2 个物品放入了背包
第 2 个物品放入了背包*/
System.out.println("============================");
// i j 初始化指向二维数组v[][]的最后一个单元格，即为0-1背包问题的最优解（背包中物品的最大价值）
// 循环判断第i个物品是否放入了容量为j的背包中（path[i][j] == 1），
// 如果放入了，则求出背包的剩余容量（j -= weight[i-1]），继续判断第i-1（i--）个物品是否放入容量为j的背包中
// 如果没放入，则判断前一个物品（i--）是否放入了容量为j的背包中
// weight[i-1] 解释：i的初始值为i = path.length - 1（i=3），代表最后一个物品，但是在weight[]中
// 最后一个物品的下标索引为2，索引要 i - 1 指向最后一个物品
int i = path.length - 1;
int j = path[0].length - 1;
while(i > 0 && j > 0 ) {
if(path[i][j] == 1) {
System.out.println("第 " + i + " 个物品放入了背包，" + "其重量为 " + weight[i-1] + "，价值为 " + value[i-1]);
j -= weight[i-1];
}
i--;
}
/*第 2 个物品放入了背包，其重量为 2，价值为 30
第 1 个物品放入了背包，其重量为 1，价值为 40*/
}
}