0-1背包问题

Author Avatar
Binbin Xu 2月 25, 2016

背包问题是一个非常经典的问题，今天我们就来讨论其中的一种：0-1背包问题

1. 问题描述

给出n个物品的体积A[i]和其价值V[i]，将他们装入一个大小为m的背包，最多能装入的总价值有多大？

为什么叫0-1背包问题呢，题目中假设每一种背包只有装和不装两种情况，我们不可能装入两个A[0]的物品，所以叫0-1背包问题

2. 转移方程

我们构造一个二维的转移数组dp[i][j]，表示前面i个物品放入总体积为j的背包中所获得的最大价值，那么：

1
2
dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i]] + V[i]);
// dp[i-1][j]表示不放入物品A[i], dp[i-1][j-A[i]] + V[i]表示放入物品A[i]所得到的最大价值

由于实际编程中物品的下标是从0开始的，我们对上面的方程做一下修改

1
dp[i+1][j] = max(dp[i][j], dp[i][j-A[i]] + V[i]);

那么程序就是

1
2
3
4
5
6
7
8
9
10
11
12
int backPack(int m, vector<int> A, vector<int> V) {
        vector<vector<int> > dp(A.size()+1, vector<int>(m+1, 0));
        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j <std::min(A[i], m+1); j++) {
                dp[i+1][j] = dp[i][j];
            }
            for (int j = A[i]; j <= m; j++) {
                dp[i+1][j] = std::max(dp[i][j], dp[i][j-A[i]] + V[i]);
            }
        }
        return dp[A.size()][m];
}

如果觉得i+1比较难受，也可以这么写：

1
2
3
4
5
6
7
8
9
10
11
12
int backPack(int m, vector<int> A, vector<int> V) {
        vector<vector<int> > dp(A.size()+1, vector<int>(m+1, 0));
        for (int i = 1; i <= A.size(); i++) {
            for (int j = 0; j <std::min(A[i], m+1); j++) {
                dp[i][j] = dp[i-1][j];
            }
            for (int j = A[i]; j <= m; j++) {
                dp[i][j] = std::max(dp[i-1][j], dp[i-1][j-A[i]] + V[i]);
            }
        }
        return dp[A.size()][m];
}

3. 优化

3.1 二维变一维

从转移方程可以看到，实际当前i的所有状态都只依赖于i-1，所以上面的二维数组很容易优化到一维：

1
2
3
4
5
6
7
8
9
10
11
12
int backPack(int m, vector<int> A, vector<int> V) {
    // write your code here
    vector<int> dp(m+1, 0);
    for (int i = 0; i < A.size(); i++) {
        vector<int> new_dp = dp;
        for (int j = A[i]; j <= m; j++) {
            new_dp[j] = std::max(dp[j], dp[j-A[i]] + V[i]);
        }
        dp = new_dp;
    }
    return dp[m];
}

3.2 再优化

虽然上面的程序已经优化到一维了，但同时维护着两个一维数组，我们也已经说过当前i的所有状态都只依赖于i-1，那么我们是否可以只用一个一维数组呢，答案是肯定的，如下：

1
2
3
4
5
6
7
8
9
10
int backPack(int m, vector<int> A, vector<int> V) {
    // write your code here
    vector<int> dp(m+1, 0);
    for (int i = 0; i < A.size(); i++) {
        for (int j = m; j >= A[i]; j--) {
            dp[j] = std::max(dp[j], dp[j-A[i]] + V[i]);
        }
    }
    return dp[m];
}

这里要注意一个问题我们的for (int j = m; j >= A[i]; j--)是反着写的，正着写是有问题的，如果j从小到大的话，dp[j-A[i]]可能已经被更新过了，而我们需要的是前一轮的dp[j-A[i]]，而反着写就没什么问题。

我另外有一篇文章完全背包问题，有兴趣的读者可以去查看一下！

Powered by Hexo
Theme - Material