动态规划

b站上一个up主关于动态规划的教学,有助于理解动态规划的主要思想

基本介绍

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

动态规划算法最佳实践-背包问题

背包问题:有一个背包,容量为4磅 , 现有如下物品:

物品 重量 价格
吉他(G) 1 1500
音响(S) 4 3000
电脑(L) 3 2000

要求:

目标为装入的背包的总价值最大,并且重量不超出
装入的物品不能重复

背包问题思路分析

背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品,如何选择物品放入背包使物品的价值最大。其中又分01背包和完全背包(完全背包指的是:每种物品都有无限件可用)
这里的问题属于01背包,即每个物品最多放一个。而无限背包可以转化为01背包。

解决类似的问题可以分解成一个个的小问题进行解决,假设存在背包容量大小分为1,2,3,4的各种容量的背包(分配容量的规则为最小重量的整数倍):

例如:

物品 0 磅 1磅 2磅 3磅 4磅
0 0 0 0 0
吉他(G) 0
音响(S) 0
电脑(L) 0

对于第一行(i=1), 目前只有吉他可以选择,所以

物品 0 磅 1磅 2磅 3磅 4磅
0 0 0 0 0
吉他(G) 0 1500(G) 1500(G) 1500(G) 1500(G)
音响(S) 0
电脑(L) 0

对于第二行(i=2),目前存在吉他和音响可以选择,所以

物品 0 磅 1磅 2磅 3磅 4磅
0 0 0 0 0
吉他(G) 0 1500(G) 1500(G) 1500(G) 1500(G)
音响(S) 0 1500(G) 1500(G) 1500(G) 3000(S)
电脑(L) 0

对于第三行(i=3),目前存在吉他和音响、电脑可以选择,所以

物品 0 磅 1磅 2磅 3磅 4磅
0 0 0 0 0
吉他(G) 0 1500(G) 1500(G) 1500(G) 1500(G)
音响(S) 0 1500(G) 1500(G) 1500(G) 3000(S)
电脑(L) 0 1500(G) 1500(G) 2000(L) 3500(L+G)

对上面填表过程进行分析:

  1. 对第一行和第一列填表,都是0

  2. 当要放入的商品重量大于当前列表示的重量时,table[ i ] [ j ] = table[ i-1 ] [ j ]

    例如:存在吉他和音响可以选择时,由于音响是4磅,所以1、2、3磅这几列放不了音响,所以直接使用上一个单元格的装入策略。

  3. 当要放入的商品重量小于或等于当前列表示的重量时

    • 不放入该商品,table[ i ] [ j ] = table[ i-1 ] [ j ]
    • 放入该商品,table[ i ] [ j ] = value[该商品价值] + table[ i-1 ] [当前列表示的重量 - 该商品重量]
    • 根据最大价值选择放入或不放入该商品

背包问题的代码实现

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
package com.nanzx.dynanic;

public class KnapsackProblem {

public static void main(String[] args) {
int[] weight = { 1, 4, 3 };// 每件物品的重量
int[] value = { 1500, 3000, 2000 };// 每件物品的价格
int maxWeight = 4;// 背包的最大容量

// table[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值
int[][] table = new int[weight.length + 1][maxWeight + 1];
int[] goods = new int[3];// 记录放入物品的情况

// 动态规划处理table这个二维数组
for (int i = 1; i < table.length; i++) {
for (int j = 1; j < table[i].length; j++) {
if (weight[i - 1] > j) {
table[i][j] = table[i - 1][j];
} else {
table[i][j] = Math.max(table[i - 1][j], value[i - 1] + table[i - 1][j - weight[i - 1]]);
}
}
}

// 遍历table这个二维数组
for (int i = 0; i < table.length; i++) {
for (int j = 0; j < table[i].length; j++) {
System.out.print(table[i][j] + " ");
}
System.out.println();
}

int j = maxWeight;
for (int i = table.length - 1; i > 0; i--) {// 从最后一格向前遍历
if (table[i][j] == table[i - 1][j]) {// 使用上一个单元格的装入策略,说明没有装入该物品
goods[i - 1] = 0;
} else {
goods[i - 1] = 1;
j = j - weight[i - 1];
}
}

// 输出我们是放入了哪些商品
for (int i = 0; i < goods.length; i++) {
if (goods[i] == 1) {
System.out.printf("第%d个商品放入到背包\n", i + 1);
}
}
}
}

运行结果:

0 0 0 0 0
0 1500 1500 1500 1500
0 1500 1500 1500 3000
0 1500 1500 2000 3500
第1个商品放入到背包
第3个商品放入到背包