跳转至

img

完全背包

一、问题引出

现在一共有 \(N\) 件物品，第i（i从1开始）件物品的重量为 \(v[i]\) ，价值为 \(w[i]\) 。每个物品可以挑选 无数次 ，且在挑选出来的物品的总重量不超过 \(V\) 的情况下，能装入背包的物品的总价值和最大为多少

二、分析

现在我们对每一个物品的抉择就不只是 “选” 和 “不选” 了，因为现在每一个物品可以选择无限次，但是我们的背包容量还是有限制的，假设说一个背包全装第 \(i\) 个物品，那么最多装 \(K = \left \lfloor \frac{V}{v[i]} \right \rfloor\) 这么多个，于是我们将每一个物品的 上限次数 求出来了 那么我们的状态转移方程其实就可以写成这样:

\[F[i][j] = max\{F[i-1][V-k\times v[i]] + k\times w[i]\} \ (0<=k\times v[i]<= V)\]

2.1 转化为01背包

我们将这 \(K\) 个物品看作独立的物品，那么我们将每一个物品都这样拆分然后再放进我们的数组里面，最后跑一次01背包就能解决我们这个完全背包问题了,于是我们得到了如下代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1000+10,M = N * N;
int v[M],w[M],n,V;

int f[N];

int main()
{
    cin>>n>>V;
    int a,b;
    int cnt = 0;
    for(int i = 1;i <= n; ++i) {
        cin>>a>>b;
        for(int j = 1,l = V/a;j <= l; ++j) //将其拆分为单个物品
            v[++cnt] = a,w[cnt] = b;
    }

    for(int i = 1;i <= cnt; ++i)
        for(int j = V;j >= v[i]; --j)
            f[j] = max(f[j],f[j-v[i]] + w[i]);
    cout<<f[V]<<endl;

}

2.2 空间优化

上面将完全背包问题转化为了01背包问题，但是带来了一个问题，如果每一件物品拆分的次数都很多，导致超出了空间限制，那怎么办呢，实际上我们不用将每一个物品直接放进我们的 \(v[]\) 和 \(w[]\) 数组，我们只需要在状态转移的时候用到就好了，于是我们得到了这个代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1000+10,M = N * N;
int v[N],w[N],n,V;

int f[N];

int main()
{
    cin>>n>>V;
    int a,b;
    int cnt = 0;
    for(int i = 1;i <= n; ++i)  cin>>v[i]>>w[i];

    for(int i = 1;i <= n; ++i)
        for(int j = V;j >= v[i]; --j)
            for(int k = 1,l = V/v[i]; k <= l; ++k)
                if(j >= v[i] * k)
                    f[j] = max(f[j],f[j - v[i] * k] + w[i] * k);
    cout<<f[V]<<endl;

}
这里需要注意两个点：

  • 1.我们循环背包的大小的时候需要从后往前循环
  • 2.我们在 for 循环的时候 背包空间 的循环是要放在 次数枚举 循环的上面的，如果我们将空间枚举放在最里层，表示的含义就是对于k个物品，每一个可选可不选，那么最后覆盖的范围就会发生重复，这一点其实可以和下面的时间优化做一个对比

2.3 时间优化

对于我们枚举一个物品取 \(K\) 次的时候其实是可以通过 二进制优化 的，我们来思考这样一个问题，如果有了 \(1、2、4\) 三位数我们就能拼凑出 \([1,7]\) 范围内所有的数，那么如果我们想凑出 \([1,12]\) 范围内所有的数呢，我们还需要再条件一个数 \(5\) ，那么由于我们前面能拼凑出 \([1,7]\) 范围内的数，那么我们再添加一个 \(5\) 就能扩大我们拼凑的数的范围 \([1,12]\) ，对于我们这个集合的每一个数我们可以通过选择或者是不选来实现所有数位的枚举，而这就类似我们的二进制一样 0 表示的就是不选， 1 表示的就是选择，那么这样的话我们并不需要把k种物品的选法从0枚举完，只需要将其二进制拆分出来然后一一枚举即可，而这一部分的内容其实是放在了 多重背包 部分的，关于完全背包其实有更加优秀的优化方法，故在此就不多赘述关于二进制优化的细则了，关于代码大家可以先自己思考一下，在下一章的多重背包会细谈的

2.4 常数优化

  • 若两件物品 \(i、j\) 满足 \(v_i ≤ v_j\) 且 \(w_i ≥ w_j\)，则将可以将物品 \(j\) 直接去掉，不用考虑。

这个优化的正确性是显然的：任何情况下都可将价值小费用高的 \(j\) 换成物美价廉的 i，得到的方案至少不会更差。对于随机生成的数据，这个方法往往会大大减少物品的 件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的 数据可以一件物品也去不掉。

  • 首先将体积大于 \(V\) 的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以 \(O(V + N)\) 地完成这个优化。

一般来说背包问题都不会卡常，故上述优化代码就不给出代码了，根据实际问题分析吧

2.5 最优优化

在前面的二进制优化的地方我们讲了，对于完全背包有着比二进制优化更加好的一个优化，那么我们现在先来看看上面的状态转移方程：

\[F[i][j] = max\{F[i-1][V-k\times v[i]] + k\times w[i]\} \ (0<=k\times v[i]<= V)\]

我们观察可以知道，如果我们要将这一件物品放入我们的背包中假设不枚举 \(k\) 那应该是怎样呢？

  • 不放入第 \(i\) 件物品，即 \(f[i][j]=f[i-1][j]\)

  • 放入第 \(i\) 件物品，即 \(f[i][j] = f[i][j-v[i]]+w[i]\) 因为这样装载的话新的状态就会覆盖久的状态，也就造成了对于一个物品我们可以选择无限次的情况，而这种效果正是我们想要的（在前面的01背包处我们也讲过了）

那么不难得出代码如下： 

#include<bits/stdc++.h>
using namespace std;

const int N = 1000+10,M = N * N;
int v[N],w[N],n,V;

int f[N][N];

int main()
{
    cin>>n>>V;
    int a,b;
    for(int i = 1;i <= n; ++i)  cin>>v[i]>>w[i];

    for(int i = 1;i <= n; ++i)
        for(int j = 0;j <= V; ++j){
            if(j >= v[i])
                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][V]<<endl;

}
注意的是，我们这里 \(f[i][j]\) 的状态如果在 \(j\) 比 \(v[i]\) 小的时候应该由上一层直接转移过来

然后我们发现其实第一层状态我们去掉不会影响状态转移，因为我们如果是新一层那么直接先由上一层转移过来就好了，如果还是当前这一层那么也直接由 \(j-v[i]\) 的状态转移过来就好，总而言之我们通过滚动优化可以去掉一个维度，得到如下代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1000+10,M = N * N;
int v[N],w[N],n,V;

int f[N];

int main()
{
    cin>>n>>V;
    int a,b;
    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 <= V; ++j)
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    cout<<f[V]<<endl;

}
现在我们的时间复杂度就变成了 \(O(NV)\) ,而空间复杂度变成了 \(O(V)\)

2.6 小结

至此我们的完全背包内容大概如上，完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程。希望读者能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。

事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。

三、题单

多加练习能够更快的掌握完全背包的精髓，故附上题单：

题目 链接 题解
疯狂的采药 https://www.luogu.com.cn/problem/P1616
[USACO3.1]Score Inflation https://www.luogu.com.cn/problem/P2722
神奇的四次方数 https://www.luogu.com.cn/problem/P1679
A+B Problem（再升级） https://www.luogu.com.cn/problem/P1832
投资的最大效益 https://www.luogu.com.cn/problem/P1853
Cut Ribbon https://www.luogu.com.cn/problem/CF189A
Elimination https://www.luogu.com.cn/problem/CF417A
[USACO08NOV]Buying Hay S https://www.luogu.com.cn/problem/P2918
[CSP-J2019] 纪念品 https://www.luogu.com.cn/problem/P5662
[NOIP2018 提高组] 货币系统 https://www.luogu.com.cn/problem/P5020
整数划分 https://www.acwing.com/problem/content/description/902/ https://acmer.blog.csdn.net/article/details/123052271
最后更新: 2022-03-07 08:58:56

评论

回到页面顶部