记录生活中的点点滴滴

0%

动态规划算法(背包问题)

动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解 的处理算法 。

与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。 ( 即下一个子 阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解 ) 。

动态规划可以通过填表的方式来逐步推进,得到最优解。

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

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

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

(1)要求达到的目标为装入的背包的总价值最大,并且重量不超出

(2)要求装入的物品不能重复

总体思路

根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出01背包问题的最优解以及解组成,然后编写代码实现。

动态规划的原理

动态规划与分治法类似,都是把大问题拆分成小问题,通过寻找大问题与小问题的递推关系,解决一个个小问题,最终达到解决原问题的效果。但不同的是,分治法在子问题和子子问题等上被重复计算了很多次,而动态规划则具有记忆性,通过填写表把所有已经解决的子问题答案纪录下来,在新问题里需要用到的子问题可以直接提取,避免了重复计算,从而节约了时间,所以在问题满足最优性原理之后,用动态规划解决问题的核心就在于填表,表填写完毕,最优解也就找到。

最优性原理是动态规划的基础,最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质:不论初始状态和初始决策如何,对于前面决策所造成的某一状态而言,其后各阶段的决策序列必须构成最优策略”。

背包问题的解决过程

每次遍历到的第 i 个物品,根据 w[i]和 v[i]来确定是否需要将该物品 放入背包中。即对于给定的 n 个物品,设 v[i]、w[i]分别为第 i 个物品的价值和重量,C 为背包的容量。再令 v[i][j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值。则我们有下面的结果:

1
2
3
4
5
6
7
8
9
(1) v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是 0
(2) 当 w[i]> j 时:v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于 当前背包的容量时,就直接使用上一个
单元格的装入策略
(3) 当 j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
// 当 准备加入的新增的商品的容量小于等于当前背包的容量,
// 装入的方式:
v[i-1][j]: 就是上一个单元格的装入的最大值
v[i] : 表示当前商品的价值
v[i-1][j-w[i]] : 装入 i-1 商品,到剩余空间 j-w[i]的最大值

这样我们就完成了填表找到了商品的最优解,但是最优解由哪些商品构成,我们却不知道,所以我们还有定义一个 item 一维数组,根据回溯法求解出最优解商品构成,在 item 上将其下标标记为1。有如下寻解方式:

  • V(i,j)=V(i-1,j)时,说明没有选择第i 个商品,则回到V(i-1,j);
  • V(i,j)=V(i-1,j-w(i))+v(i)时,说明装了第i个商品,该商品是最优解组成的一部分,随后我们得回到装该商品之前,即回到V(i-1,j-w(i));
  • 一直遍历到i=0结束为止,所有解的组成都会找到。

以上所有代码如下:

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
//动态规划算法:背包问题 求解实现
public class KnapsackProblem {
//物品
public static final String things[] = {"", "吉他(G)","音响(S)","电脑(L)"};
//重量
public static final int weight[] = {0,1, 4, 3};
//价格
public static final int price[] = {0,1500, 3000, 2000};

//有things.length行,要计算到4磅,所以5列
static int row = things.length;
static int column = 4 + 1;
//v[i] w[i]分别表示第i个物品的价值和重量
//V[i][j] 表示前i个物品中能够装入容量为j的背包中的最大价值
static int[][] V = new int[row][column];
static int[] w = weight;
static int[] v = price;
//最优解的商品构成,对应下标为1
static int[] item = new int[row];

public static void main(String[] args) {
//让V[i][0]和V[0][j] = 0,表示填入第一行和第一列为0,默认为0,所以不用再写

//求出V
findMax();
//遍历输出V
list();
//求解最优解的组成情况
findWhat(row-1,column-1);
//输出最优解的组成情况
printWhat();
}

//求出V
public static void findMax(){
for (int i = 1; i < row; i++) {
for (int j = 1; j < column; j++) {
if(w[i]>j){
V[i][j] = V[i-1][j];
}else {
V[i][j] = Math.max(V[i-1][j],v[i]+V[i-1][j-w[i]]);
}
}
}
}
//遍历输出V
public static void list(){
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
System.out.printf("%d\t",V[i][j]);
}
System.out.println();
}
}
//求解最优解的组成情况
public static void findWhat(int i, int j){
if(i==0)
return;
if(V[i][j] == V[i-1][j]){//说明不包含第i个商品
findWhat(i-1,j);
}else if(j-w[i]>=0 && V[i][j] == v[i]+V[i-1][j-w[i]]){
item[i] = 1;
findWhat(i-1,j-w[i]);
}
}
//输出最优解的组成情况
public static void printWhat(){
System.out.print("最优解的商品构成:");
for (int i = 1, len = item.length; i < len; i++) {
if(item[i] == 1){
System.out.print(things[i]+" ");
}
}
System.out.println();
}
}

运行结果: