动态规划

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磅这几列放不了音响，所以直接使用上一个单元格的装入策略。

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

    • 不放入该商品，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个商品放入到背包