动态规划算法
应用场景—0-1背包问题
背包问题：有一个背包，容量为4磅，现有物品如下
| 物品 | 重量 | 价格 |
|---|---|---|
| 吉他（G） | 1 | 1500 |
| 音响（S） | 4 | 3000 |
| 电脑（L） | 3 | 2000 |
要求：
达到目标为装入的背包的总价值最大，且重量不超出
要求装入的物品不可重复
动态规划算法介绍
动态规划（Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，熊二一步步获取最优解的处理算法
与分治算法类似，但不同的是动态规划子问题不相互独立
动态规划可以通过填表的方式来逐步推进，得到最优解
解决0-1背包问题
主要思想
利用动态规划来解决，每次遍历到第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品，令：
w[i]：第i个商品的重量
val[i]：第i个商品的价值
C：背包容量
v[i][j :表示前i个物品中能够装入容量为j的背包中的最大价值
则有下列结论：
v[i][0] = v[0][j] = 0;
当w[i] > j时：v[i][j] = v[i-1][j]
当j >= w[i]时：v[i][j] = max{v[i-1][j],v[i-1][j-w[i]] + val[i]}
思路图解
背包的填表过程
-
物品还未装入背包,初始状态
行,0磅,1磅……代表背包容量,哪一行表示可以放入此行及 以上行的物品,但是哪一行先方哪一行的物品
列,代表物品在对应背包容量下各自在背包中的价格
物品 0磅 1磅 2磅 3磅 4磅 0 0 0 0 0 吉他（G） ０ 音响（S） ０ 电脑（L） ０ -
加入现在只有吉他此时不论背包容量有多大,只能放一把吉他
物品 0磅 1磅 2磅 3磅 4磅 0 0 0 0 0 吉他（G） ０ 1500(G) 1500(G) 1500(G) 1500(G) 音响（S） ０ 电脑（L） ０ -
假如有吉他和音响,当背包容量同时满足多个物品时,考虑哪个物品价值更高将其放入
物品 0磅 1磅 2磅 3磅 4磅 0 0 0 0 0 吉他（G） ０ 1500(G) 1500(G) 1500(G) 1500(G) 音响（S） ０ 1500(G) 1500(G) 1500(G) 3000(S) 电脑（L） ０ -
假如由吉他,音响,电脑时,先放电脑,放完之后如果有空余空间可以放入其他物品则放入,否则不用再关心
物品 0磅 1磅 2磅 3磅 4磅 0 0 0 0 0 吉他（G） ０ 1500(G) 1500(G) 1500(G) 1500(G) 音响（S） ０ 1500(G) 1500(G) 1500(G) 3000(S) 电脑（L） ０ 1500(G) 1500(G) 2000(L) 2000(L) + 1500(G) 则有下列结论：
//表示填入的表的第一行和第一列置0
v[i][0] = v[0][j] = 0;
//当新增加商品时,若新商品大于背包容量时,则直接使用上一单元格的装入策略
当w[i] > j时：v[i][j] = v[i-1][j]
//当新增加商品时,其容量小于背包容量,
//装入的策略:
//1. v[i-1][j]上一单元格的价值
//2. v[i-1][j-w[i]] + v[i]当前商品的 价值+剩余空间装入物品价值的最大 值
//3. 此时比较装入商品的价值,使用价值最 大的策略
当j >= w[i]时：v[i][j] = max{v[i-1][j],v[i-1][j-w[i]] + val[i]}
代码实现
package whyAlgorithm.dynamic;
import java.util.Arrays;
/**
* @Description TODO 动态规划解决0-1背包问题
* @Author why
* @Date 2020/12/9 21:04
* Version 1.0
**/
public class KnapsackProblem {
public static void main(String[] args) {
int[] w = {1,4,3};//物品重量
int[] val = {1500,2000,3000};//物品价值
int m = 4;//背包容量
int n = val.length;//物品个数
//为记录放入商品的情况，定义一个二维数组
int[][] path = new int[n+1][m+1];
//创建二维数组
//v[i][j]表示前i个物品能够装入容量为j的背包中最大的价值
int[][] v = new int[n+1][m+1];
//初始化第一行和第一列,在本程序中可以不处理，因为默认为0
for (int i = 0; i < v.length; i++) {
//将第一列置为0
v[i][0] = 0;
//将第一行置为0
v[0][i] = 0;
}
//根据前面的公式动态规划处理
for (int i = 1; i < v.length; i++) {//不处理第一行
for (int j = 1; j < v[0].length; j++) {//不出来第一列
//公式
//因为i从1开始，故原公式修改为 w[i] = w[i-1]
if (w[i-1] > j){
v[i][j] = v[i-1][j];
}else {
//int b = v[i-1][j-w[i-1]] + val[i-1];
//int max = Math.max(v[i - 1][j], b);
//v[i][j] = max;
//为了记录商品存放到背包的情况不能简单地使用上面的公式，需要使用if，else体现这个公式
if (v[i-1][j] < v[i-1][j-w[i-1]] + val[i-1]){
v[i][j] = v[i-1][j-w[i-1]] + val[i-1];
//记录当前情况
path[i][j] = 1;
}else {
v[i][j] = v[i-1][j];
}
}
}
}
System.out.println("分配表：");
for (int i = 0; i < v[0].length-1; i++) {
System.out.println(Arrays.toString(v[i]));
}
//输出放入的哪些商品
//遍历path，这样输出会有误，我们要最后的放入
// for (int i = 0; i < path.length; i++) {
// for (int j = 0; j < path[0].length; j++) {
// if (path[i][j] == 1){
// System.out.printf("第%s个商品放入到背包\n",i);
// }
// }
// }
int i = path.length - 1;//行的最大下标
int j = path[0].length - 1;//列的最大下标
while (i > 0 && j > 0){//从path数组的最后开始找
if (path[i][j] == 1){
System.out.printf("第%s个商品放入到背包\n",i);
j -= w[i-1];
}
i--;
}
}
}