完全背包问题

什么是完全背包问题

小明期末考试得了全班第一名，妈妈给了他一个背包，可以去超市任意选购，可以选购多种商品，每种商品可以选购多个，但是选择的商品必须都放在背包里。

超市很大，有很多种商品：火腿，雪糕，饼干 ·····。每种商品都摆满了货架。不同商品的体积和价值不同。文章源自灵鲨社区-https://www.0s52.com/bcjc/cyyjc/16291.html

在背包能装下的前提下，小明想尽可能带回价值总量高的商品，请问他能带回的商品的最大价值是多少？文章源自灵鲨社区-https://www.0s52.com/bcjc/cyyjc/16291.html

这就是完全背包问题。文章源自灵鲨社区-https://www.0s52.com/bcjc/cyyjc/16291.html

有 N 种物品和一个背包，每种物品的数量无限。给出了每种物品的体积 v 和价值 w 以及背包的容量 V。文章源自灵鲨社区-https://www.0s52.com/bcjc/cyyjc/16291.html

求解 : 背包能装下的前提下，所能获得的最大价值。文章源自灵鲨社区-https://www.0s52.com/bcjc/cyyjc/16291.html

例如我们有 4 种物品和一个容量为 5 的背包。这四种物品对应的体积和价值分别是：文章源自灵鲨社区-https://www.0s52.com/bcjc/cyyjc/16291.html

• 物品一：体积是 1，价值是 2。
• 物品二：体积是 2，价值是 4。
• 物品三：体积是 3，价值是 4。
• 物品四：体积是 4，价值是 5。

我们可以选择把 1 个 物品一 和 1 个 物品四 放入背包，体积是 1 + 4 = 5，没有超过背包容量，价值是 2 + 5 = 7。文章源自灵鲨社区-https://www.0s52.com/bcjc/cyyjc/16291.html

我们可以选择把 1 个 物品一 和 2 个 物品二 放入背包，体积是 1 + 2 + 2 = 5，没有超过背包容量，价值是 2 + 4 + 4 = 10。文章源自灵鲨社区-https://www.0s52.com/bcjc/cyyjc/16291.html

我们可以选择把 2 个 物品一 和 1 个 物品三 放入背包，体积是 1 + 1 + 3 = 5，没有超过背包容量，价值是 1 + 1 + 4 = 6。文章源自灵鲨社区-https://www.0s52.com/bcjc/cyyjc/16291.html

还有其它选法。文章源自灵鲨社区-https://www.0s52.com/bcjc/cyyjc/16291.html

我们的目的是，找到能被背包装下的物品的最大价值。

动态规划解题步骤

动态规划问题一般从三个步骤进行考虑。

步骤一:集合和集合的状态

所谓的集合，就是一些方案的集合。

用 g[i][j] 表示从前 i 种物品中进行选择，且总体积不大于 j 的各个选法获得的价值的集合。注意：g[i][j] 不是一个数，是一堆数。

例如 g[2][3] 从前 2 种物品中进行选择，且总体积不大于 3 的各个选法获得的价值的集合。

g[2][3] 的可选择方案包括：

• 方案一：都不选，总价值为 0。
• 方案二：选 1 件 物品 1，总价值为 2。
• 方案三：选 2 件物品 1，总价值为 4。
• 方案四：选 3件 物品 1，总价值为 6。
• 方案五：选 1 件物品 2，总价值为 4。
• 方案六：选 1 件物品 2，一件物品 1，总价值为 6。

所以 g[2][3] = {0，2，4，6，4，2}。

i j 取不同的值，对应不同的 g[i][j]，也就是对应不同的集合。

用 f[i][j] 表示从前 i 种物品中进行选择，总体积小于等于 j 所能获得的最大价值。很明显，f[i][j] 就是 g[i][j] 中的最大值。i j 取不同的值，就对应不同的 f[i][j]。我们把 f[i][j] 叫做集合的状态。

例如 f[2][3] 表示从前 2 种物品中进行选择，且总体积不大于 3 的获得的最大价值。f[2][3] = max(g[2][3] ) = max( 0，2，4，6，4，2) = 6。

g[i][j] 的最大值就是 f[i][j]。

如果我们能把所有集合对应的最大值都求出来，即求出了 f[0][0] ~ f[N][V]， f[N][V] 的含义是在前 N 种物品中进行选择，总体积不大于 V 所获得的最大价值，就是我们要找的答案。

注意，我们不需要把各个集合的所有元素都找出来，只需要求出各个集合的最大值，就能找到答案。下面就是如何求出各个集合的最大值。

步骤二：状态计算

g[i][j] 是从前 i 种物品中进行选择，且总体积不大于 j 的各个选法获得的价值的集合。

f[i][j] 是从前 i 种物品中进行选择，总体积小于等于 j 所能获得的最大价值。

f[i][j] 是集合 g[i][j] 的最大值。

所谓的状态计算是指，如何将把 f[i][j] 算出来。

如果把各个集合 g[i][j] 的状态 f[i][j] 求出来， f[N][V] 就是要找的答案。

回想一下 0 1 背包问题。

01 背包问题把 g[i][j]划分成了 A B 两部分，分别求出这两个部分对应的最大值，然后两者取最大值就是整体 g[i][j] 的最大值，就是 f[i][j]。

01 背包根据是否选择第 i 件物品，也就是第 i 件物品选 0 个还是 1 个，把 g[i][j] 划分成了 A B 两部分，分别求出这两个部分的最大值，然后两者取最大值就是整体 g[i][j] 的最大值，也就求出了 f[i][j]。

完全背包问题也是根据第 i 件物品的选择数量，把 g[i][j] 划分成不同的部分，分别求出各个部分的最大值，取各个部分最大值中的最大值，就是整体 g[i][j] 的最大值，也就求出了 f[i][j]。

因为每种物品的数量是无限的，根据第 i 种物品的选择数量可以把 g[i][j] 分为这样几部分：

• A 部分： 第 i 种物品选 0 件。
• B 部分：第 i 件物品选 1 件。
• C 部分： 第 i 件物品选 2 件。
• X 部分： 第 i 件物品选 x 件。

. . . . .

因为选择物品的总体积不能 j，所以第 i 件物品最多选j / vi 向下取整件。

• 对于 A 部分：第 i 件物品选 0 件。等价于从前 i - 1 种物品中选择商品，且总体积不超过 j 的各个价值的集合，也就是 g[i - 1][j]。g[i - 1][j] 这个集合中的最大值是 f[i - 1][j] ，所以 A 部分的最大值就是 f[i - 1][j]。
• 对于 B 部分：第 i 件物品选 1 件， 1 个 i 物品会占据 vi的背包空间，剩下的背包空间为 j - vi 。可以从前 i - 1 种物品中，选出总体积小于等于j - vi 的物品放入背包。
• 从前 i - 1 种物品中，选出总体积小于等于j - vi 的各个方案获得的价值集合为 g[i - 1][j - vi ? ? ]，所以 B 部分的元素为 g[i - 1][j - vi ? ? ] 中各个元素加上 wi。g[i - 1][j - vi ? ? ] 中的最大值为 f[i - 1][j - vi ? ? ]，所以 B 部分的最大值为 f[i - 1][j - vi ? ? ] + wi。
• 对于 X 部分：第 i 件物品选 x 件， x 个 i 物品会占据 x * vi的背包空间，剩下的背包空间为 j - x * vi。可以从前 i - 1 种物品中，选出总体积小于等于j - x * vi的物品放入背包。
• 从前 i - 1 种物品中，选出总体积小于等于j - x * vi 的各个方案获得的价值集合为 g[i - 1][j - x * vi ? ? ]，所以 x 部分的元素为 g[i - 1][j - x * vi ? ? ] 中各个元素加上 x * wi 。g[i - 1][j - x * vi ? ? ] 中的最大值为 f[i - 1][j - x * vi ? ? ]，所以 B 部分的最大值为 f[i - 1][j - x * vi ? ? ] + x * wi

例如 g[2][4]。

第二种物品的体积为 2，选择物品的总体积不能超过 4。所以第二件物品可以选择：0件、1件、2件。

因此 g[2][4] 可以分成以下几部分：

• A 部分：第二件物品选 0 件。A 部分的最大值为： f[i - 1][j - 0 * vi ? ? ] + 0 * wi 。
• B 部分：第二件物品选 1 件。B部分的最大值为： f[i - 1][j - 1 * vi ? ? ] + 1 * wi 。
• C 部分：第二件物品选 2 件。C 部分的最大值为：f[i - 1][j - 2 * vi ? ? ] + 2 * wi。

g[2][4] 中的最大值为 max(A，B，C)。

通过上面分析，我们可以知道，g[i][j] 可以分成若干部分:

• A 部分是第 i 种物品选 0 个对应所有选法获的价值的集合，最大值是 f[i - 1][j]。
• B 部分是第 i 种物品选 1 个对应所有选法获的价值的集合，最大值是 f[i-1][j - vi ? ? ] + wi。
• X 部分是第 i 种物品选 x 个对应所有选法获的价值的集合，最大值是 f[i - 1][j - x * wi ? ? ]。
• 所以 g[i][j] 的最大值就是所有子集的最大值中最大的那个，也就是 f[i][j] = max(A, B ，····) 即：
• 

展开式为：f[i] [j] = max( f[i-1][j] , f[i - 1][j - vi ? ? ]+w , f[i - 1][j - 2 * vi ? ? ] + 2 * w , f[i - 1][j - k * vi ? ? ] + k * w , .....) 其中 k <= j / w。

从计算公式可以看出:

• f[i][j] 是由 f[i - 1][j - k * vi ? ? ] (0 <= k <= j / wi) 和 wi 计算出来的。
• f[i][j]的值是可以从前面已经计算出的 f 值求出来。
• 如果我们能确定 f[i][j] 的一部分初始值，就能通过该公式，一步步计算得出 f[N][V]，也就是我们要找的答案。

步骤三：确定初始值

完全背包问题的有些状态是能够直接确定的。

例如 f[0][0]。

f[0][0] 的含义是:

• 从前 0 种物品中选择，并且选出的物品总体积小于等于0 时所能得到的最大价值。
• 总体积小于等于 0，说明一种物品都不能选择。
• 因此 f[0][0] = 0。同理 f[1][0] = 0，f[2][0] = 0 ··· f[N][0] = 0。

有了这些初始值，通过 i 从 1 遍历 N，j 从 1 遍历 V，第 i 种物品的选择数量 k 从 0 遍历到 j / wi就能一步步求出所有的 f[i][j] 了。

例如求 f[1][1]：

f[1][1] = max{f[0][1]，f[0][0] + 2} = max(0，2) = 2。

求 f[1][2]：

f[1][2] = max{f[0][2]，f[0][1] + 2，f[0][0] + 4} = max(0，2，4) = 4。

最后 f[N][V] 就是要找的答案。

这时候就可以写代码了：

#include<iostream>
using namespace std;

const int N = 1010;

int n, m;
int f[N][N], v[N], w[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];
    for(int i = 0; i <= m; i++)//初始化
    {
        f[0][i] = 0;
    }
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
            for(int k = 0; k * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);//求出每一个 f[i][j]
    cout << f[n][m] << endl;
}

优化

动态规划的优化一般都是对代码或者状态计算方程进行一个等价变形。在考虑动态规划问题的时候，一定要先把基本的形式写出来，然后再对它进行优化。

看一下 f[i][j] 和 f[i][j - vi ? ? ] 的求解公式：

f[i][j] = max( f[i-1][j] , f[i-1][j - vi ? ? ] + w , f[i-1][j - 2 * vi ? ? ] + 2 * w , f[i-1][j - 3 * vi ? ? ] + 3 * w , .....)。
f[i][j - vi ? ? ] = max( f[i-1][j - vi ? ? ] , f[i-1][j - 2 * vi ? ? ] + w , f[i-1][j - 3 * vi ? ? ] + 2 * w , .....) 。

由上两式，可得出如下递推关系：

f[i][j] = max(f[i][j-v] + w , f[i-1][j])

更清楚的解释：

有了上面的关系，那么其实 k 循环可以不要了，核心代码优化成这样：

for(int i = 1; i <= n; i ++ )
    {
        for(int j = 0; j <= m; j ++ )
        {
            if(v[i] <= j)//第 i 种能放进去
                f[i][j] =max(f[i - 1][j], f[i][j - v[i]] + w[i]);
            else//如果第 i 件物品不能放进去
                f[i][j] = f[i - 1][j];
        }
    }

完整代码：

#include<iostream>
using namespace std;

const int N = 1010;

int n, m;
int f[N][N], v[N], w[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 0; j <= m; j ++ )
        {
            if(v[i] <= j)
                f[i][j] =max(f[i - 1][j], f[i][j - v[i]] + w[i]);
            else
                f[i][j] = f[i - 1][j];
        }
    }
    cout << f[n][m] << endl;
}

接着对比下完全背包的核心代码与 0 1 背包的核心代码：

f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包

f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题

//0 1 背包代码优化这里有详细说明

因为和 0 1背包代码很相像，我们很容易想到进一步优化。核心代码可以改成下面这样:

for(int i = 1 ; i<=n ;i++)
    for(int j = v[i] ; j<=m ;j++)//注意了，这里的j是从小到大枚举，和01背包不一样
    {
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    }

综上所述，完全背包的最终写法如下：

#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1 ; i <= n ;i ++)
    {
        cin>>v[i]>>w[i];
    }

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

}

完全背包问题到此解决。

完全背包问题的思维导图：