背包问题

动态规划算法

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》,这是该领域的第一本著作。

题型

背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。
问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?

解法

寻找状态转移方程
F(n, c) = max(F(n-1, c), F(n-1,c-i)+vi)(n≥1, c≥wi)
利用状态转移方程式自底向上求解问题
即买还是不买,若是买,则找出买后背包剩余空间的最大价值(上一轮循环)加上当前价值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {
int c = 10;
int[] w = {2, 5, 4, 4, 1};
int[] v = {5, 10, 10, 5, 1};

int[] results = new int[c + 1];
for (int n = 1; n <= w.length; n++) {
for (int j = c; j >= 1; j--) {
if (j>=w[n-1]) {
results[j] = Math.max(results[j], results[j - w[n - 1]] + v[n - 1]);
}
}
}
System.out.println(results[c]);
}}