脚本宝典收集整理的这篇文章主要介绍了背包问题的处理，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

背包问题的一些拓展与处理

装箱问题

题目描述：

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

核心思想

(f[i])记录当体积为m时，最多能放多少

转移方程：(f_j=max(f_j,f_{j-u}+u))

特殊性:此处的价值和容量是同一个东西

宠物小精灵之收服

题目描述

有一个背包，第一个容量是M,第二个容量是V，共有N个物品，问最多能装几个，此时第二个容量最多能剩多少

(0<N≤1000) (0<M≤500) (0<V≤100)

核心思想：

这题本来是一个朴素的二维费用背包问题，但是这题有两个值得深究的点：

1.怎么去找最多能装几个，最多能剩多少

我们设(f_{i,j})表示(m)为(i)，(v)为(j)时所收集到的最大精灵。

然后我们就可以列出一个平凡的三重循环的DP

但是还没有完，我们要求的最多能装几个好说，怎么求能剩多少呢

这也好办，如果此时的(f_{i,j})比(ans)数组要大，那么(tag)直接标记成(j)

但是如果两者相等，就取两者较小的

最后直接输出即可

int f[N][N],u[N],v[N];
int n,m,q,tagans,tag;
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=q;i++) scanf("%d%d",&u[i],&v[i]);
    for(int i=1;i<=q;i++)
        for(int j=n;j>=u[i];j--)
            for(int k=m;k>=v[i];k--)
                f[j][k]=max(f[j][k],f[j-u[i]][k-v[i]]+1);
    for(int j=0;j<=n;j++){
        for(int k=0;k<m;k++){
            if(f[j][k]>tagans) tagans=f[j][k],tag=k;
            else if(f[j][k]==tagans && tag>k) tag=k;
    printf("%d %d",tagans,m-tag);
    return 0;
}

2.我们观察数据发现什么

第一种写法的时间复杂度我们容易发现是(O(nmV))

我们首先可以理解一个问题就是对于一个背包来说，(f_{i,j})表示枚举第(i)样物品的体积是(j)时的最大价值

那么此时的(v[i])和(w[i])是可以互换的，只是会更改(f)数组的意义

那我们回来看这个题，由于(V)很小，我们考虑多次使用(V)

所以我们的新的(f)数组表示v为(i), 枚举到第(j)个物品用了最小的(m)

所以我们此时就可以换一种写法

const int inf=0x3f3f3f3f;
int f[N][N];
int n,m,q;
int main(){
    memset(f,0x3f,sizeof(f));
    scanf("%d%d%d",&n,&m,&q);
    f[0][0]=0;
    for(int i=1,u,v;i<=q;i++){
        scanf("%d%d",&u,&v);
        for(int j=m;j>=v;j--)
            for(int k=i;k;k--)
                if(f[j-v][k-1]+u<=n) f[j][k]=min(f[j][k],f[j-v][k-1]+u); 
    }
    for(int k=q;~k;k--)
        for(int j=0;j<m;j++)
            if(f[j][k]!=inf) return printf("%d %dn",k,m-j),0; 
    return 0;
}

这时候我们分析复杂度就是(O(V^2m))算出来大概是5e6,前面那个算出来是5e7，区别还是很大的

看一眼两者的时间差，确实差距还是有的

数字组合

题目描述：

给定(n)个正整数(A1,A2,…,An)，从中选出若干个数，使它们的和为(m)，求有多少种选择方案。

(1≤n≤100) (1≤m≤10000) (1≤Ai≤1000)

核心思想：

这个题是要求方案数，是一类很经典的DP了

首先，我们要设(f_{j})表示和为(j)的方案数

那么对于(j)来说，假如说存在(i∈[1,n])且(a[i]+k=j)那么我们的(f[j]=f[j]+f[k])就是说(f_k)的所有方案数都可以通过加上一个数凑成(j)，所以我们可以得出(f_j+=f_j-a[i])

因为每个数只能选一次，所以我们直接用01背包操作即可

注意：f[0]要赋成1

int f[N],a[N];
int n,m;
int main(){
    read(n),read(m);
    f[0]=1;
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++){
        for(int j=m;j>=a[i];j--){
            f[j]=f[j]+f[j-a[i]];
        }
    }
    cout<<f[m];
    return 0;
}

货币系统

题目描述：

给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。

核心思想：

这个题和上一个题差不多，但是我们发现我们的当前的加钱可以有若干张统一价钱的拼接起来，直接完全背包就行了啊

#define int long long
int f[N];
signed main(){
    int n,m;
    cin>>n>>m;
    f[0]=1;
    for(int i=1;i<=n;i++){
        int u; cin>>u;
        for(int j=u;j<=m;j++) f[j]+=f[j-u];
    }
    cout<<f[m];
    return 0;
}

混合背包问题

题目描述

有(N)种物品和一个容量是 (V) 的背包。

物品一共有三类：

• 第一类物品只能用1次（01背包）；
• 第二类物品可以用无限次（完全背包）；
• 第三类物品最多只能用 (si) 次（多重背包）；

每种体积是(vi),价值是(wi)。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

核心思想：

我们考虑一个问题我们在二进制优化时我们是把每个物品拆分，那么此时我们可以直接套用二进制拆分的思想，01背包就转化成(s=1)的多重背包，完全背包转化为(s=m/u)的多重背包

最后用多重背包思路求解即可QAQ

#include <bits/stdc++.h>
using namespace std;
int n,m,v[100010],w[100010],f[100010];
int main(){
    cin>>n>>m;
    int cnt=1;
    for(int i=1;i<=n;i++){
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        if(s<0)s=1;
        else if(s==0)s=m/a;
//把01背包和多重背包先转化成多重背包，若为完全背包，则在最优情况下，只能取总体积/该物品体积向下取整 
        while(k<=s){
            v[cnt]=a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2;
            cnt++;
        }
        if(s>0){
            v[cnt]=s*a;
            w[cnt]=s*b;
            cnt++;
        }
    }//将多重背包进行二进制优化，变成01背包 
    for(int i=1;i<=cnt;i++){
        for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]); //01背包问题
    cout<<f[m]<<endl;
    return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的背包问题的处理全部内容，希望文章能够帮你解决背包问题的处理所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。