程序员常用十大算法(三):动态规划算法(填表法）解决01背包问题_动态规划填表法

动态规划算法（填表法）

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

案例引入：

背包问题：
现有一个背包，可以放4斤东西，有如下物品：

1.要求达到的目标是装入背包的总价值最大，并且重量不超出背包容量
2.要求装入的物品不重复
（另外一种情况是无限背包：即每种物品都有无限件可放。我们这里先用不可重复背包为例）

思路分析：
解决类似的问题可以分解成一个个的小问题进行解决，假设存在背包容量大小分别为1，2，3，4的各种容量的背包（分配容量的规则的为最小重量的整数倍）
如图：

物品第一行为空表示无物品装入背包，此时不管背包容量多大，总价值都为0
第二列为空表示背包容量为空，此时不管物品多少总价值也都为0
第一步：
假如只有手机，这时不管背包容量多大，只能放一个吉他（不能重复）

第二步：
假如有手机和笔记本，当背包容量只有1斤时，只能放个手机：

当背包容量有两斤和三斤时，仍放不下笔记本；

当背包容量有四斤时，可放一部手机或一个笔记本，发现C(笔记本）>C(手机）（C表示价值）
所以：

第三步：
三样齐全：

思路解析：

• i表示表格中的行
• j表示表格中的列
• w[i]:第i个物品的重量
• v[i]:第i个物品的价值
• v[i][j]:表示在前i个物品中能够装入容量为j的背包中的最大价值。
  每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中 。于是有：
  1）v[i][0]=v[0][j]=0;
  (当背包容量为0时或物品价值为0时最大价值为0）
  2）当w[i]>j时：v[i][j]=v[i-1][j]
  (当第i个物品重量大于背包的容量时，就直接使用i-1（即上一个）物品的装入策略
  3）当j>=w[i]时：v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+v[i]}
  (当准备装入的新增的商品的容量小于当前背包的容量，
  装入的方式：
  v[i-1][j]:就是上一个物品装入时的最大值
  j-w[i-1]为装入i后电脑剩下的空间这些剩下的空间可装的价值加上已经加入的价值
  以此与上一个价值（即v[i-1][j]的价值）进行比较，看哪个大。

如果上面的公式看不明白的话，请看如下举例：
首先我们以第三步中的图为例，
假如现在有手机和笔记本
验证公式：
v[1][1]=1500（即1斤容量的背包装一个手机的价值）
1）当i=1时，j=1
2)w[i]=w[1]=1
w[1]=1 j=1 带入公式：
v[i][j]=max{v[i-1][j],v[i]+v[i-1]-w[i]}:
得
v[1][1]=max{v[0][1],v[1]+v[0][1-1]}=max{0,1500}

验证公式：
v[3][4]
1)i=3;j=4
w[i]=w[3]=3;j=4
j=4大于w[i]=3
v[3][4]=max{v[2][4],v[3]+v[2][1]}=max{3000,2000+1500}=3500

代码实现

package dynamic;

public class KnapsackProblem {
	public static void main(String[] args) {
		int[] w= {1,4,3};//物品重量
		int[] val= {1500,3000,2000};//物品价值
		int m=4;//背包容量
		int n=val.length;//物品个数
		
		//创建二维数组，表
		//v[i][j]:表示在前i个物品中能够装入容量为j的背包中的最大价值。
		int[][] v=new int[n+1][m+1];

		
		//初始化第一行和第一列
		for(int i=0;i<v.length;i++) {
			v[i][0]=0;//讲第一列设置为0
		}
		for(int i=0;i<v[0].length;i++) {
			v[0][i]=0;//将第一行设置为0
		}
		
		//根据前面得到得公式来动态规划处理
		for(int i=1;i<v.length;i++) {//从1开始，不处理第一行
			for(int j=1;j<v[0].length;j++) {//不处理第一列
				//套用公式：(i从1开始，公式中得w[i]和val[i]中的i需减一
				if(w[i-1]>j) {
					v[i][j]=v[i-1][j];
				}else {
					v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
				}
			}
		}
		//打印表：
		for(int i=0;i<v.length;i++) {
			for(int j=0;j<v[i].length;j++) {
				System.out.print(v[i][j]+" ");
			}
			System.out.println();
		}
		
	}
}

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