完全背包

问题描述

有N种物品和一个容量为V 的背包，每种物品都有无限件可用。放入第i种物品的费用是wi，价值是vi。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

算法思想

朴素思想

完全背包与01背包不同的是同一种物品可多次选取。有了01背包的基础，再来理解完全背包就很容易了。

先回顾一下01背包的状态转移方程：

• j<w(i) V(i,j)=V(i-1,j)
• j>=w(i) V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝

完全背包的子问题定义和01背包相同，V(i,j)表示当前背包容量 j，前 i 个物品最佳组合对应的价值。面对当前商品也同样有两种可能性：

1. 包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
2. 还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，装多少也同样是个未知数。所以我们需要另设一个变量k表示装的物品的个数（0<=k*wi<=j）。我们需要在装k个物品之间选择最优的一个，即V(i,j)=max｛V(i-1,j-k*w(i))+k*v(i)｝。
   其中k=0时比较特殊，原式变为V(i,j)=V(i-1,j)表示不装。V(i-1,j-k*w(i))+k*v(i) 表示装了k个第物品i，背包容量减少k*w(i)，但价值增加了k*v(i)；

由此可得出完全背包的状态转移方程：

• j<w(i) V(i,j)=V(i-1,j)
• j>=w(i) V(i,j)=max｛V(i-1,j-k*w(i))+k*v(i)｝（0<=k<=floor(j/wi)）

核心代码如下：

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        if (j < w[i])
            dp[i][j] = dp[i - 1][j];
        else
            for (int k = 0; k <= j / w[i]; k++)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
    }
}

本来01背包就是两重for循环，现在又加了k需要遍历，可以预想到需要三重for循环，时间复杂度是极高的，这自然是不行的。所以我们需要优化。

优化思想

将原始算法的DP思想转变一下：

1. 对于第i种物品的出现，我们对第i种物品放不放入背包进行决策。如果不放那么V(i,j)=V(i-1,j)；
2. 如果确定放，背包中应该出现至少一件第i种物品，所以V(i,j)中至少应该出现一件第i种物品，即V(i,j)=V(i,j-wi)+vi。为什么会是V(i,j-wi)？因为V(i,j-wi)里面可能有第i种物品，也可能没有第i种物品。我们要确保V(i,j)至少有一件第i件物品，所以要预留wi的空间来存放一件第i种物品。

那么完全背包和 01 背包的不同点在哪里呢？

从二维数组上区别 01 背包和完全背包，也就是状态转移方程就差别在放第 i 种物品时，完全背包在选择放这个物品时，最优解是 V(i,j)=max｛V(i-1,j-k*w(i))+k*v(i)｝即同行的那一个，而 01 背包比较的是V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝，上一行的那一个。

由此可得出优化后的完全背包状态转移方程：

• j<w(i) V(i,j)=V(i-1,j)
• j>=w(i) V(i,j)=max｛V(i-1,j)，V(i,j-wi)+vi｝

核心代码如下：

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        if (j < w[i])
            dp[i][j] = dp[i - 1][j];
        else
            dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
    }
}

最优解回溯

具体背包中放入哪些物品的求法和01背包情况差不多，从dp[n][m]逆着走向dp[0][0]，设i初值为物品种数，j初值为背包容量，如果dp[i][j]==dp[i][j-w[i]]+v[i]说明包里面有第i件物品，同时j -= w[i]。

完全背包问题在处理i自减和01背包不同，01背包是不管dp[i][j]与dp[i-1][j-w[i]]+v[i]相不相等i都要减1，因为01背包的第i件物品要么放要么不放，不管放还是不放其都已经遍历过了，需要继续往下遍历而完全背包只有当dp[i][j]与dp[i-1][j]相等时i才自减1。因为dp[i][j]=dp[i-1][j]才能说明背包里面不会含有i，也就是说对于前i种物品容量为j的背包全部都放入前i-1种物品才能实现价值最大化，或者直白的理解为前i种物品中第i种物品物不美价不廉，直接被筛选掉。

核心代码如下：

while (i > 0 && j > 0)
{
    if (dp[i][j] == dp[i][j - w[i]] + v[i])
    {
        j -= w[i];
        item[i] += 1;//item数组记录第i个物品装几个才能实现价值最大化
    }
    else
        i -= 1;
}

代码实现

输入格式：

第一行两个整数n，m表示物品种数及背包容量

接下来n行每行两个整数分别表示第i种物品的体积和价值

要求输出一个整数表示最大价值总和

样例输入：

3 70

71 100

69 1

1 2

样例输出：

140

c++实现：

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 1001;
int dp[MAX][MAX]; //dp[i][j]表示当前容量为j，前i种物品最佳组合对应的价值
int w[MAX];       //用于保存体积的数组
int v[MAX];       //用于保存价值的数组
int item[MAX];    //记录第i个物品拿几个才能价值最大化

void findWhat(int n, int j)
{
    int i = n;
    while (i > 0 && j > 0)
    {
        if (dp[i][j] == dp[i][j - w[i]] + v[i])
        {
            j -= w[i];
            item[i] += 1;
        }
        else
            i -= 1;
    }
    for (int k = 1; k <= n; k++)
        cout << item[k] << " ";
    cout << endl;
}

int main()
{
    int n, m;
    cin >> n >> m;
    //输入体积和价值
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];
    //设置边界
    for (int i = 0; i <= n; i++)
        dp[i][0] = 0;
    for (int i = 0; i <= m; i++)
        dp[0][i] = 0;
    //开始动规
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (j < w[i])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
        }
    }
    cout << dp[n][m] << endl;

    // findWhat(n, m); //输出最优解
    return 0;
}

空间优化

观察下面完全背包的核心代码：

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        if (j < w[i])
            dp[i][j] = dp[i - 1][j];
        else
            dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
    }
}

和01背包一样，整个状态转移过程中我们只用到了dp数组的第i行和第i-1行，把数组优化成两行当然也是完全没问题的

不过，这里我们要说的是可以优化到一维数组。再回到代码，我们可以发现j<w[i]时，我们只是把dp[i-1][j]的数据照搬了过来，其实并没有什么操作，如果用一维数组来刻画的话就是：现在这个一维数组里存的相当于是i-1行的数据，然后我们要转变为第i行还是存在这个数组里，j<w[i]时就相当于保留原数据。

再看else情况下，这就和01背包有点区别了。01背包同样也只涉及第i-1行，但完全背包第i-1行和第i行都涉及到了。如果按照01背包从后往前遍历的思路的话，由于dp[i][j-w[i]]要用到第i行前面的数据，但前面的数据要等j减到一定程度才生成，所以这是行不通的，完全背包需要从前往后遍历。

j从0开始往后遍历的时候，当一开始j小于w[i]时，对于第i种物品，背包肯定是放不下的，我们没有选择的余地，也就是说上面代码中的if-else判断走的必然是if。用二维数组的时候就是dp[i][j] = dp[i - 1][j]。放在一维数组的视角下其实就相当于没操作。所以j可以直接从w[i]开始遍历，但对于dp[w[i]]之前的数据虽说没有动它，但其实已经属于第i行的了。

当j后面增加到大于w[i]时，对于上面的核心代码里的if-else判断，肯定走的是else。第i-1行的数据仍在数组里，第i行前面的数据也有了，那自然就可以去掉i那一维了。

优化后的核心代码：

for (int i = 1; i <= n; i++)
{
    for (int j = w[i]; j <= m; j++)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}

完整代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 1001;
int dp[MAX]; //dp[i][j]表示当前容量为j，前i种物品最佳组合对应的价值
int w[MAX];  //用于保存体积的数组
int v[MAX];  //用于保存价值的数组

int main()
{
    int n, m;
    cin >> n >> m;
    //输入体积和价值
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];
    //设置边界
    for (int i = 0; i <= n; i++)
        dp[i] = 0;
    //开始动规
    for (int i = 1; i <= n; i++)
    {
        for (int j = w[i]; j <= m; j++)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
    cout << dp[m] << endl;
    return 0;
}