算法之动态规划算法的介绍，以及案例介绍与是实现
1 动态规划
1.1 介绍
动态规划（Dynamic Programming） 算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
动态规划算法和分治算法类似，核心解题思想都是一样
不同点 为：适合用动态规划求解的问题，经过分解后得到的子问题往往不是互相独立的（下一个子阶段的求解是建立在上一个子阶段的基础上，进一步求解）
动态规划可以通过填表的方式来逐步推出，得到最优解
2 01背包问题
2.1 题目
2.2 思路
创建两个数组，来记录商品的 重量(weight) 以及 价值(value) ；创建一个二维数组，用来记录商品之间组合的最大价值，类似 填表的方式 ；表的横坐标为表示背包容量，纵坐标为可填入背包的器材，填表方式具体如下:
| 图解 |
|---|
 |
 |
 |
 |
 |
- 思路总结：
- （1）优先比较新增商品重量与当前背包重量，大于背包重量，价值等于上一行的价值。反之进入下一步
- （2）计算商品价值：新增商品价值 + 上一行当前剩余背包容量的价值
- （3）比较计算后的价值与上一行的价值，计算价值>上一行价值，填入计算价值，反之填入上一行价值
2.3 代码
- （1）01背包问题类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105/**
* 01背包
* @author letere
* @create 2021-06-06 10:59
*/
public class Knapsack01 {
//物品名称
private String[] items;
//物品价值
private int[] value;
//物品重量
private int[] weight;
//背包容量
private int size;
//最大价值表格（纵坐标：物品，横坐标：背包容量）
private int[][] valueTable;
//装配策略
private Map<String, Integer>[][] strategy;
//构造器
public Knapsack01(String[] items, int[] value, int[] weight, int size) {
this.items = items;
this.value = value;
this.weight = weight;
this.size = size;
int row = items.length + 1;
int column = size + 1;
this.valueTable = new int[row][column];
this.strategy = new HashMap[row][column];
//二维数组初始化，因为最大价值表int默认为0，所以不需要
for (int i=0; i<row; i++) {
for (int j=0; j<column; j++) {
strategy[i][j] = new HashMap<>();
}
}
}
/**
* 计算最优装配策略
*/
public void calculateBest() {
int val;
//跳过第0行，从第1行开始计算
for (int row=1; row<items.length+1; row++) {
for (int column=0; column<size+1; column++) {
//重量 > 背包容量，等于上一行价值
//row-1才是items, value, weight数组对应的下标
if (weight[row-1] > column) {
valueTable[row][column] = valueTable[row-1][column];
strategy[row][column].putAll(strategy[row-1][column]);
}else {
//计算价值：新增商品价值 + 上一行当前剩余背包容量价值
val = value[row-1] + valueTable[row-1][column-weight[row-1]];
//比较当前计算价值与上一行的价值
if (valueTable[row-1][column] > val) {
valueTable[row][column] = valueTable[row-1][column];
strategy[row][column] = strategy[row-1][column];
}else {
valueTable[row][column] = val;
strategy[row][column].putAll(strategy[row-1][column-weight[row-1]]);
strategy[row][column].put(items[row-1], 1);
}
}
}
}
System.out.println("最大价值为：" + valueTable[items.length][size]);
System.out.println("装配策略为：" + strategy[items.length][size]);
}
/**
* 打印价值表
*/
public void printValueTable() {
System.out.println("最大价值表格为：");
for (int[] row : valueTable) {
for (int column : row) {
System.out.print(column + "\t");
}
System.out.println();
}
}
/**
* 打印装配策略表
*/
public void printStrategy() {
System.out.println("装配策略表为：");
for (Map<String, Integer>[] row : strategy) {
for (Map<String, Integer> column : row) {
System.out.print(column + "\t");
}
System.out.println();
}
}
}
- （2）测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void knapsack01Test() {
String[] items = new String[]{"吉他", "音响", "电脑"};
int[] value = new int[]{1500, 3000, 2000};
int[] weight = new int[]{1, 4, 3};
int size = 4;
Knapsack01 knapsack01 = new Knapsack01(items, value, weight, size);
knapsack01.calculateBest();
System.out.println("------------------");
knapsack01.printValueTable();
System.out.println("------------------");
knapsack01.printStrategy();
}
