动态规划之 0-1 背包问题详解

前言

背包问题是比较经典的动态规划算法题,之前没接触过算法都没听说过这个,也是后来在 leetcode 中刷题时才了解到,惭愧惭愧啊。算法的世界太奇妙,数学一直都是那么令人着迷。今天来总结一下这个 01 背包问题。注:这里的物品不可拆分。

动态规划

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

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

详情可见:动态规划

问题详解

问题描述

给定 N 种物品和一个背包。物品i的重量是 Wi,其价值位 Vi,背包的容量为 C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大。

问题分析

在选择物品的时候,对每种物品只有两种选择,要么装入,要么不装入。因此,此为一个 0-1 背包问题。
01 背包的递归公式为:

1
2
3
m[i,0] = m[0,j] = 0
m[i,j] = m[i-1,j] ,j < wi
m[i,j] = max(m[i-1,j-wi]+vi, m[i-1,j]) ,j >= wi

其中,m[i,j]为前 i 件物品中选择若干件,放入承重为 j 的背包中,得到的最大的价值。

wi 为第 i 件商品的重量。

vi 为第 i 件商品的价值。

例题讲解

有编号为 a,b,c,d,e 的五件物品,他们的重量分别为 4,5,6,2,2,价值分别为 6,4,5,3,6,现在给你一个承重为 10 的背包,怎么实现价值最大。

根据上述公式可以得到一个数据表,表从上向下生成:

name weight value 1 2 3 4 5 6 7 8 9 10
a 4 6 0 0 0 6 6 6 6 6 6 6
b 5 4 0 0 0 6 6 6 6 6 10 10
c 6 5 0 0 0 6 6 6 6 6 10 11
d 2 3 0 3 3 6 6 9 9 9 10 11
e 2 6 0 6 6 9 9 12 12 15 15 15

故可以根据公式码出如下实现代码:

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
public static void main(String[] args) {

int n = 5;// 5件物品,物品编号为a,b,c,d,e(下面为多加一件物品,第一个物品为虚拟的物品)
int weight[] = { 0, 4, 5, 6, 2, 2 };// 物品的重量
int value[] = { 0, 6, 4, 5, 3, 6 }; // 对应物品的价值
int c = 10; // 背包容量
int state[] = { 0, 0, 0, 0, 0, 0 };// 开始状态
char name[] = { ' ', 'a', 'b', 'c', 'd', 'e' };
int maxValue = getMaxValue(n, weight, value, state, c);
System.out.println("最大价值为 = " + maxValue);
System.out.print("放入的物品为 :");
for (int i = 1; i <= 5; i++) {
if (state[i] == 1) {
System.out.print(name[i] + " ");
}
}

// System.out.println();
}

/**
*
* @param n
* 物品数量
* @param weight
* 物品对应重量(数组下标从0开始,故第一个物品为虚拟物品)
* @param value
* 物品对应价值(数组下标从0开始,故第一个物品为虚拟物品)
* @param state
* 物品的开始状态
* @param c
* 背包的容量
* @return
*/
public static int getMaxValue(int n, int weight[], int value[], int state[], int c) {
// n 为物品的数量,数组时需要加 1,此时可以从 0,1,...n 个物品,共 n+1 个商品,其中第 0 个为虚构物品
// 对于物品的价值,可以写成 2 维数组
int m[][] = new int[n + 1][c + 1]; // n 为 0,1,2...(n-1),背包重量为 0,1,2...C
int i, j;

for (i = 0; i <= n; i++) {
m[i][0] = 0;
}
for (j = 0; j <= c; j++) {
m[0][j] = 0;
}

for (i = 1; i <= n; i++) {
// System.out.println();
for (j = 1; j <= c; j++) {
if (j < weight[i]) { // 新的物品太重,无法放下
m[i][j] = m[i - 1][j];
} else {// 分为放和不放 取较大值
m[i][j] = Math.max(m[i - 1][j - weight[i]] + value[i], m[i - 1][j]);
}
// System.out.print("m["+i+"]["+j+"]="+m[i][j]+" ");
// System.out.print(m[i][j]+" ");
}
}

// 根据其最大价值,反向推断是否添加了物品 i

j = c;
for (i = n; i > 0; i--) {
if (m[i][j] > m[i - 1][j]) {// 物品 i 添加到了序列列表
state[i] = 1;
j = j - weight[i];
} else { // 没有添加
state[i] = 0;
}
}

return m[n][c]; // 最大价值
}

输出结果为:

1
2
最大价值为 = 15
放入的物品为 :a d e

具体实现看上述代码即可,注释齐全,简单易懂。

参考资料

文章作者: Folgerjun
文章链接: http://putop.top/2018/09/26/DP-01backpack/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 DoubleFJ の Blog