总目录：地址如下看总纲
1、动态规划算法介绍
1、动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
2、动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
3、与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
4、动态规划可以通过 填表 的方式来逐步推进，得到最优解
2、动态规划算法最佳实践-背包问题
有一个背包，容量为4磅 ， 现有如下物品
要求：
1、要求达到的目标为装入的背包的总价值最大，并且重量不超出
2、要求装入的物品不能重复
3、思路分析（文字说明）
1、背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。
2、其中问题分两种，01背包 和 完全背包(完全背包指的是：每种物品都有无限件可用)
3、这里的问题属于01背包，即每种类物品最多放一个。而无限背包可以转化为01背包。
4、算法的主要思想，利用动态规划来解决。每次遍历到的第i个物品，根据 w[i] 和 v[i] 来确定是否需要将该物品放入背包中。v[i][j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值，公式和解释如下：
（1） w[i] 表示 第 i 个商品的重量， v[i] 表示 第 i 个商品的价值(价格) ，j 表示 当前背包的容量
（2） v[i][0] = v[0][j] =0; //表示 填入表 第一行和第一列是0
（3） 当w[i]> j 时：v[i][j] = v[i-1][j] ; // 当准备加入新增的商品的容量大于 当前背包的容量时，就直接使用上一个单元格的装入策略 (阿K解释：就是现在月薪很低的你买不起贵的，你只能买得起和上个月月薪一样的东西...)
（4） 当 j>=w[i] 时： v[i][j] = max{v[i-1][j], v[i]+v[i-1][j-w[i]]} ; // 当 准备加入的新增的商品的容量小于等于当前背包的容量（其中max 内的参数分两个 ，比较出最大的一个 ，赋值 给 v[i][j]）,具体解释：
v[i-1][ j ] ： 既上一个单元格的装入的最大值（已有的值）
v[ i - 1 ] [ j - w[ i ] ] ： 装入i-1商品，到剩余空间为 j-w[i] 的最大值
注：此二位数组可以看成 x轴和 y 轴， v[y] [x] 或者 v[i] [j]，以后表格对应，x轴对应的是 重量(容量)，y轴则是 物品编号
4、思路分析（图分解）
（1）背包问题：有一个背包，容量为4磅 ， 现有如下物品，
要求达到的目标为装入的背包的总价值最大，并且重量不超出。
（2）解决类似的问题可以分解成一个个的小问题进行解决，假设存在背包容量大小分为1，2，3，4的各种容量的背包(分配容量的规则为最小重量的整数倍)：
（3）第一次填表：对于第一行(i=1), 目前只有吉他可以选择，所以
（4）第二次填表：对于第二行(i=2),目前存在吉他和音响可以选择,所以
（5）第三次填表：对于第三行(i=3),目前存在吉他和音响、电脑可以选择,所以
（★）带数推导公式案例：
- 案例一：v[1][1] = ? ，已知 ： w[1] = 1 ， j = 1 （已知数据从价格表中获得）
v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+v[i]} = v[1][1] = max{v[0][1], v[0][0]+v[1]} = max{0, 0 + 1500}，其中v[1]是第一件物品 吉他的价格 - 案例二：v[3][4] = ? ，已知： w[3] = 3 ， j >= w[3] （已知数据从价格表中获得）
v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+v[i]} = v[3][4] = max{v[2][4],v[2][1]+v[3] = max{3000,1500+3000}，其中v[1]是第三件物品 电脑的价格
★注意：看表格的时候，记得物品是3 件，默认添加一件 不存在的 ，角标从0开始，总的是 4件(3+1)，数组角标 0 到 3 ，归属 y（i） 轴坐标 v[ y] [ x ] ；容量(重量) 是 4 磅(个单位)，默认一个单位不存在，角标从 0开始， 总的是 5 件(4 + 1)，数组角标 0 到 4 ，归属 x（j）轴，坐标 v[ y ] [ x] 。
5、代码
package com.kk.algorithm.dynamic;
/*
* @Description: 动态规划(背包问题)
* @Author: Jk_kang
* @CreateDate: 2021/2/5 0:25
* @Param:
* @Return:
**/
public class KnapsackProblem {
public static void main(String[] args) {
// 物品的重量
int[] w = {1, 4, 3};
// 物品的单价(价值)，此处的val[i] 既 v[i] ,某个物品的单价
int[] val = {1500, 3000, 2000};
// 背包容量(总的或者部分)，因为它是可变的，代码中体现
int m = 4;
// 物品个数
int n = w.length;
// 构建二位数组(表格)
// v[i][j] 表示在第i个物品中能够装入容量为j的背包中的最大价值
int[][] v = new int[n + 1][m + 1];
// 为了记录放入商品的情况，我们定一个二维数组
int[][] table = new int[n + 1][m + 1];
// 初始第一行，第一列，默认为 0 可以不设置，但是我愿意！
for (int i = 0; i < v.length; i++) {
// 初始第一列
v[i][0] = 0;
}
for (int i = 0; i < v[0].length; i++) {
// 初始第一列
v[0][i] = 0;
}
// 根据思路，进行动态规划实现
for (int i = 1; i < v.length; i++) {// 第一行不处理，因为默认为0
for (int j = 1; j < v[0].length; j++) {// 第一列不处理，因为默认为0
// 公式 w[i] > j 实现
if (w[i - 1] > j) {// 因为 从1 开始，因此公式 w[i] 需改为 w[i-1]
v[i][j] = v[i - 1][j];
} else {
// 故因：i 从 1 开始，公式做调整
// 原公式：v[i][j] = Math.max (v[i - 1][j], v[i] + v[i - 1][j - w[i]]);
// 修改为：v[i][j] = Math.max (v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
// val[] 中 -1 因为数组从 0 开始，这边循环直接从 1 开始所以 -1；
// w[] 中 -1 也同上理
//为了记录商品存放到背包的情况，我们不能直接的使用上面的公式，需要使用if-else来体现公式
if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {// 如果上一个单元格，小于最新添加的剩余最大值
v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
// 则把情况记录
table[i][j] = 1;// 记录当前坐标为最优，用状态 1 表示
} else {
// 若新增不是最优，就和上个单元格一致
v[i][j] = v[i - 1][j];
}
}
}
}
//输出一下v 看看目前的情况
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 ( );
}
//错误输出, 这样输出会把所有的放入情况都得到, 其实我们只需要最后的放入
// for(int i = 0; i < table.length; i++) {
// for(int j=0; j < table[i].length; j++) {
// if(table[i][j] == 1) {
// System.out.printf("第%d个商品放入到背包\n", i);
// }
// }
// }
//正确输出：逆向输出最后一个商品的 排列顺序
int i = table.length - 1; //行的最大下标
int j = table[0].length - 1; //列的最大下标
while(i > 0 && j > 0 ) { //从table 的最后开始找
if(table[i][j] == 1) {// 坐标满足最优
System.out.printf("第%d个商品放入到背包\n", i);
j -= w[i-1]; //w[i-1]，查找一个物品后 减去对应的重量
}
i--;// 查找一个物品后 -1
}
}
}
6、坐标
