背包问题变式总结

拼搏现实的明天。 2024-03-23 23:47 33阅读 0赞

## 01背包 ##

### 01背包完全装满求方案数 ###

> [Acwing 278 数字组合][Acwing 278]

状态表示：二维

集合：所有从前 i 个数里面选，且和是 j 的选法的集合

属性：选法的数量

状态计算 分为 选 i 的所有方案 和 不选 i 的所有方案

不选 i 也就是从前 i−1 个数里面选，且和是 j 的方案数 f\[i−1,j\]

选 i 也就是从前 i−1 个数里面选，且和是 j−ai 的方案数，注意是 += ，因为我们算的是数量而不是最大值

注意当 j=0 也是有一种方案的，要初始化为 1

#include <iostream>
    using namespace std;
    const int N = 105, M = 10005;
    int f[N][M], a[N];
    int n,m;
    int main()
    {
        cin>>n>>m;
        f[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            f[i][0]=1;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                f[i][j]+=f[i-1][j];
                if(j>=a[i]) f[i][j]+=f[i-1][j-a[i]];
            }
        }
        cout<<f[n][m];
        return 0;
    }

优化也很简单，参考01背包的优化方式

这里不过多赘述，上代码

#include <iostream>
    using namespace std;
    const int N = 10005;
    int f[N];
    int main()
    {
        int n,m;
        cin>>n>>m;
        f[0]=1;
        for(int i=1;i<=n;i++)
        {
            int a;
            cin>>a;
            for(int j=m;j>=a;j--)
                f[j]+=f[j-a];
        }
        cout<<f[m];
        return 0;
    }

### 01背包平分子集 ###

这个标题有些迷惑，什么是平分子集，有什么实际运用吗？

平分子集大体意思是给你几个数，把这些数分成两组，问你最小的差值是多少？

我们可以将数的总和记录下来，然后将这个数除以2，再从数组里面挑数字尽可能装满这个背包

解释一下：想要两个子集差值最小，那么这个值最小为0，也就是相等，那么我们就尽可能选出一些数字接近这个一半，越接近差值就越小

首先来一道比较裸的题 [巧分配][Link 1]

只需要按照上文说的方法再套上01背包的模板就行了，不过多解释

#include <iostream>
    #include <cstring>
    using namespace std;
    const int N = 50005;
    int a[N];
    int main()
    {
        int n,t;
        cin>>t;
        while(t--)
        {
            int f[N]={0};
            cin>>n;
            int sum=0;
            for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
            for(int i=1;i<=n;i++)
                for(int j=sum/2;j>=a[i];j--)
                    f[j]=max(f[j],f[j-a[i]]+a[i]);
            cout<<sum-f[sum/2]-f[sum/2]<<endl;
        }
        return 0;
    }

来一个进阶版本 [kkksc03考前临时抱佛脚][kkksc03]

题目中说的有4门学科容易误导，让人认为是分组背包什么的，实际上只相当于多组测试数据罢了，那么我们就把目光聚焦到一组上面

我们可以发现可以同时解决两个问题，那么想要这个特性运用的最划算，那么肯定是需要左脑和右脑处理的时间的差值最小，那么这个问题就转换成了平分子集问题，不过需要注意的是，这里求的是总时间，因为左脑和右脑只能处理同一科，所以如果左脑处理完了，左脑还得等右脑，所以需要取一个最大值，最后将每次取得的结果累加就行了

#include <iostream>
    #include <cstring>
    using namespace std;
    const int N = 1005;
    int s[5];
    int f[N],a[N];
    int main()
    {
        int res=0;
        for(int i=1;i<=4;i++) cin>>s[i];
        for(int t=1;t<=4;t++)
        {
            memset(f,0,sizeof f);
            int sum=0;
            for(int i=1;i<=s[t];i++) cin>>a[i],sum+=a[i];
            for(int i=1;i<=s[t];i++)
                for(int j=sum/2;j>=a[i];j--)
                    f[j]=max(f[j],f[j-a[i]]+a[i]);
            res+=max(sum-f[sum/2],f[sum/2]);
        }
        cout<<res;
        return 0;
    }

### 含有负数的01背包 ###

> [\[USACO03FALL\]Cow Exhibition G 奶牛博览会][USACO03FALL_Cow Exhibition G]

题目要求两个指数不能是负数，且和最大，不能看作简单的01背包来处理

我们可以设计一下状态，假设 TS 为正数（弄一个偏移量，把负数变成正数）。状态 f\[i\] 表示花费 i 的聪明指数能得到的最大的风趣指数

这里有几个问题需要注意一下

1.  初始化数组为负无穷，因为数据中是有正数的，其次初始化 f\[m\] 为0，表示当 TS 的值达到 0 的时候，TF 的最大值为 0
2.  我们的偏移量要是数据上限的两倍，因为枚举时出现了 −v\[i\]
3.  负数与正数要区别对待

正数和负数为什么会不一样？

在正数中，j>j−v\[i\] ，我们想要求得 f\[j\] 的话就必须要使用 i−1 层的 f\[j−TS\[i\]\] 所以如果从小到大的话会导致 f\[j−TS\[i\]\] 先算，这样用的就是 i 层的 f\[j−TS\[i\]\] 了，与原本二维的状态是不符的

而在负数中，j<j−TS\[i\] ，我们想要球的 f\[j\] 还是要用 i−1 层的 f\[j−TS\[i\]\]，如果我们从大到小的话就会导致 f\[j−TS\[i\]\] 先算，与之前是同一个道理，所以需要区别对待

#include <iostream>
    #include <cstring>
    using namespace std;
    const int N = 105, M = 200005;
    int f[M],TS[N],TF[N]; //当 TS 的值达到 i 的时候，TF 的最大值
    int main()
    {
        int n,m=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>TS[i]>>TF[i];
            if(TS[i]>0) m+=TS[i];
        }
        memset(f,-0x3f,sizeof f);
        f[m]=0;
        for(int i=1;i<=n;i++)
        {
            //正数的情况
            if(TS[i]>0)
                for(int j=m*2;j>=TS[i];j--)
                    f[j]=max(f[j],f[j-TS[i]]+TF[i]);
            //负数的情况
            else
                for(int j=0;j<=m*2+TS[i];j++)
                    f[j]=max(f[j],f[j-TS[i]]+TF[i]);
        }
        int ans=0;
        for(int i=0;i<=m;i++)
        {
            if(f[i+m]>0) ans=max(ans,f[i+m]+i);
        }
        cout<<ans;
        return 0;
    }

## 完全背包 ##

### 完全背包完全装满求方案数 ###

由于完全背包的最终版本和01背包非常像，这里就不多赘述，具体看上文提到的01背包完全装满求方案数

#include <iostream>
    using namespace std;
    const int N = 10005;
    int f[N];
    int main()
    {
        int n,m;
        cin>>n>>m;
        f[0]=1;
        for(int i=1;i<=n;i++)
        {
            int a; 
            cin>>a;
            for(int j=a;j<=m;j++)
                f[j]+=f[j-a];
        }
        cout<<f[m];
        return 0;
    }

进阶版本 [NOIP2018 提高组 货币系统][NOIP2018 _]

由于纸币有无穷张，所以是完全背包

首先来解释一下题目是什么意思，题目要求我们设计一个等价的货币系统，相当于给出的货币系统有的面值是没有用的，我们将这个货币系统优化一下，去掉几种面值，但是不能多表示一些面值，也不能少表示一些面值

那我们可以将现有的货币系统能表示的所有面值都搞出来，然后看需要什么面值的钱才能表示这个面值

换句话讲，例如说如果 5 这个面值 只有一种表示方法，那么一定是1张5元的钱，那么这张钱就不能省去，是必要的

如果有两种表示方法的话，那么就可以被替代了，由于面值只能相加不能相减，所以这两种方法其中一定有一种是由比这张钱价值小的钱凑出来的，所以我们就不需要新的钱了

另外有可能对无穷张这个点有些疑惑，无穷张不管是 2张 还是 3张 表示的面值也一定用给出的货币系统的面值凑出来，所以无需考虑

#include <iostream>
    #include <cstring>
    using namespace std;
    const int N = 25005;
    int f[N],a[105];
    int main()
    {
        int T; cin>>T;
        while(T--)
        {
            memset(a,0,sizeof a); memset(f,0,sizeof f);
            int maxx=0,ans=0;
            int n; cin>>n;
            f[0]=1;
            for(int i=1;i<=n;i++)
            {
                cin>>a[i];
                maxx=max(maxx,a[i]);
            }
            for(int i=1;i<=n;i++)
                for(int j=a[i];j<=maxx;j++)
                    f[j]+=f[j-a[i]];
            for(int i=1;i<=n;i++)
                if(f[a[i]]==1) ans++;
            cout<<ans<<endl;
        }
        return 0;
    }

## 分组背包 ##

### 分组背包完全装满求方案数 ###

> [摆花][Link 2]

与之前的一样，不过要注意的是，分组里面枚举的 k 是下标，而这里的体积都为1，所以说如果从 0 开始枚举的话要 −(k+1)

#include <iostream>
    using namespace std;
    const int N = 1005;
    int f[N];
    int main()
    {
        int n,m;
        cin>>n>>m;
        f[0]=1;
        for(int i=1;i<=n;i++)
        {
            int a; cin>>a;
            for(int j=m;j>=0;j--)
            {
                for(int k=0;k<a;k++)
                {
                    if(k<=j) f[j]=(f[j]+f[j-k-1])%1000007;
                }
            }
        }
        cout<<f[m]%1000007;
        return 0;
    }

[Acwing 278]: https://www.acwing.com/problem/content/280/
[Link 1]: http://www.nfls.com.cn:10448/barrier/2/14/8145/18053
[kkksc03]: https://www.luogu.com.cn/problem/P2392
[USACO03FALL_Cow Exhibition G]: http://www.nfls.com.cn:10448/barrier/2/14/3869/18185
[NOIP2018 _]: http://www.nfls.com.cn:10448/barrier/2/14/4841/2488
[Link 2]: http://www.nfls.com.cn:10448/barrier/2/14/5750/2502