0-1背包问题

发表于 更新于 分类于 本文字数： 1.5k 阅读时长 ≈ 1 分钟

1.问题描述

有n个物品，第i个物品的体积和价值分别为w[i]、v[i](1<= i <=n)，现有一个容量为c的背包，将这些物品选择装入该背包，如何选择使得包里的物品价值总和最大。

2.问题分析

定义函数f[i][w]表示从前i件物品中选择放入容量为w的背包能装下的物品最大价值，我们所要求的就是f[n][c]。以n为例，有两种情况:

a. 如果w[n]>c，那么n就不能选中，即f[n][c] = f[n-1][c]

b. 如果w[n] <= c, 那么n有可能选中也可能没有选中，依据就是判断选中和不选中的结果哪个大酒根据那一个，即比较f[n-1][c-w[n]]+v[n]和f[n-1][c]

3.编写代码

在解决该问题时因为每一个f都依赖上一个结果，所以需要从最小的f开始向上计算，得到结果，易得f[0][i] f[i][0]都是0，我们需要从0开始计算出所有f[][]

1
2
3
4
5
6
7
8
9
10
//i表示从前i项选择，j表示容量
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= c; j++) {
		if (w[i] > j) {
            f[i][j] = f[i - 1][j];
        } else {
            f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
        }
    }
}

完整代码如下

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
#include <iostream>
#include <cmath>
 
using namespace std;
 
int knapsack(int n, int c, int v[], int w[]) {
    int f[1001][1001] = {0};
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= c; j++) {
            if (w[i] > j) {
                f[i][j] = f[i - 1][j];
            } else {
                f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
            }
        }
    }
    return f[n][c];
}
 
int main () {
    
    int n, v[1001];
    int c, w[1001];
    
    while (cin >> n >> c) {
        for (int i = 1; i <= n; i++) {
            cin >> w[i] >> v[i];
        }
        
        cout << knapsack(n, c, v, w) << endl;
    }
    
    return 0;
}

如果想得到选择的具体情况可以通过f[i][c]-f[i-1][c]的值判断,如果f[i][c]>f[i-1][c],那么就是选取了第i个，接下来就要判断f[i - 1][c - w[i]] 和f[i - 2][c - w[i]]，注意i从大到小判断，遇到被选中的，加下来的判断就要减去这个重量

1
2
3
4
5
6
7
int w = totalWeight;
for (int i = n; i != 0; i--) {
    if (f[i][w] > f[i - 1][w]) {
        cout << i << " ";
	    w -= w[i];
    }
}