完全背包问题

Author Avatar
Binbin Xu 2月 27, 2016

之前已经讲解过0-1背包问题，今天来讨论另外一种：完全背包问题

1. 问题描述

之前0-1背包问题的问题描述如下

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

而今天要讨论的完全背包问题描述如下

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

我们可以发现区别在于：对于每一种物体，不再是之前0-1问题，而是0-k，k表示能放多个，k有可能是0，1，2…

2. 转移方程

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

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

二维的代码非常容易写，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int backPackII(int m, vector<int> A, vector<int> V) {
    // write your code here
    vector<vector<int> > dp(A.size()+1, vector<int>(m+1, 0));
    for (int i = 1; i <= n; 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++) {
            int k = 1;
            while (j-k*A[i] >= 0) {
                dp[i][j] = std::max(dp[i-1][j], dp[i-1][j-k*A[i]] + k*V[i]);
                ++k;
            }
        }
    }
    return dp[A.size()][m];
}

3. 优化

3.1 二维变一维

从转移方程可以看到，实际当前i的所有状态都只依赖于i-1，所以上面的二维数组很容易优化到一维(像0-1背包问题中可以先把二维转变成两个一维数组，在此略过)，直接给出用一个一维数组的代码：

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

这里我们的for (int j = A[i]; j <= m; j++)是正着写的，如果和0-1背包问题一样for (int j = m; j >= A[i]; j--)反着写也没有问题。

3.2 再优化

上面的代码有很多乘法和if判断，导致程序很慢，同样的测试数据上面的代码时间是1200ms左右，而下面的就260ms左右:

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

这里我们的for (int j = A[i]; j <= m; j++)是正着写的，如果是for (int j = m; j >= A[i]; j--)就会有问题。
因为我们现在是一件物品可以选0-k件，而不是0-1件，大一点的j要依赖小一点的j的dp最大值，比如小一点的j可能在k=1是取到最大值，然后大一点的j需要k=2才最大，如果反过来写for循环,那么k就只能是0或1，与题设不符合，这里需要读者细细体会！！！

Powered by Hexo
Theme - Material