动态规划算法
一、基本概念二、算法步骤及问题举例三、动态规划解决0/1背包问题代码实现
一、基本概念
动态规划算法的核心思想是：将大问题划分为小问题进行解决，从而一步一步获得最优解的处理算法。动态规划算法与分治算法类似，其基本思想也是将代求问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治算法不同的是，适合于动态规划求解的问题，经分解得到的子问题往往不是互相独立的，即下一个子阶段的求解过程是建立在上一个子阶段的解的基础上，进行进一步的求解。
二、算法步骤及问题举例
我们以一个典型的0/1背包问题来对动态规划算法进行分析。
问题描述：有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
问题举例： 有一个背包，容量为4，现有以下物品
物品重量价值
A11500B43000C32000
要求在不超过容量的前提下使装入背包的物品价值总和最大，且放入的物品不重复。
首先我们对问题中的几个变量进行抽象：
V
a
l
i
{Val_i}
Vali表示第i个物品的价值，
W
i
{W_i}
Wi表示第i个物品的重量，V(i,j)表示当前背包容量为j，前i个物品最佳组合的价值寻找递推关系：具有两种情况：
包的容量比当前待装入物品重量小，装不下，故此时的价值与前i-1个物品的价值是一样的，即V(i,j)=V(i-1,j);包的容量足够装入当前待装入物品，需要判断装入后是否达到最大价值，进而决定是否装入，即V(i,j)=max{V(i-1,j),V(i-1,j-W(i))+Val(i))}。其中V(i-1,j)表示不装入，V(i-1,j-W(i))+Val(i))表示装了第i个商品，背包容量减少w(i)但价值增加了Val(i)由以上两条可推出： (1) j<W(i) V(i,j)=V(i-1,j) (2) j>=W(i) V(i,j)=max｛ V(i-1,j)，V(i-1,j-W(i))+Val(i) } 填表： 先进行初始化
物品/重量01234
000000A(1)0B(2)0C(3)0
再按照上面的递推式依次进行填表 如：
i=1，j=1，W(1)=1，Val(1)=1500，因为j=W(1)，可以装得下，所以V(i,j)=max{V(i-1,j)，V(i-1,j-W(i))+Val(i)}=max{0,1500}=1500i=2，j=2，W(2)=4，Val(2)=3000，因为j<W(2)，装不下，所以V(i,j)=1500i=3，j=4，W(3)=3，Val(3)=2000，因为j>W(3)，可以装得下，所以V(i,j)=max{V(i-1,j)，V(i-1,j-W(i))+Val(i)}=max{3000，1500+2000}=3500
如此重复直到填表完成
物品/重量01234
000000A(1)01500150015001500B(2)01500150015002000C(3)01500150020003500
观察表格，我们可以发现，价值达到最大的方案即装入1和3，总价值为3500
三、动态规划解决0/1背包问题代码实现
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
;
int[][] v
= new int[n
+ 1][m
+ 1];
int[][] path
= new int[n
+ 1][m
+ 1];
for (int i
= 0; i
< v
.length
; i
++) {
v
[i
][0] = 0;
}
Arrays
.fill(v
[0], 0);
for (int i
= 1; i
< v
.length
; i
++) {
for (int j
= 1; j
< v
[0].length
; j
++) {
if (w
[i
- 1] > j
) {
v
[i
][j
] = v
[i
- 1][j
];
} else {
if (v
[i
- 1][j
] < val
[i
- 1] + v
[i
- 1][j
- w
[i
- 1]]) {
v
[i
][j
] = val
[i
- 1] + v
[i
- 1][j
- w
[i
- 1]];
path
[i
][j
] = 1;
} else {
v
[i
][j
] = v
[i
- 1][j
];
}
}
}
}
for (int[] a
: v
) {
System
.out
.println(Arrays
.toString(a
));
}
int i
= v
.length
- 1;
int j
= v
[0].length
- 1;
while (i
> 0 && j
> 0) {
if (path
[i
][j
] == 1) {
System
.out
.printf("第%d个商品放入背包\n", i
);
j
-= w
[i
- 1];
}
i
--;
}
}
}
测试结果：
