背包问题

背包问题

十一月 01, 2021

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

装箱问题

题目描述：

有一个箱子容量为 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$

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

最后直接输出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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$

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 %d\n",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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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的货币有多少种方案。

核心思想：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}

背包问题方案数

题目描述：

有$N$件物品和一个容量是$V$的背包。每件物品只能使用一次。

第$i$件物品的体积是$vi$，价值是$wi$。

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

输出最优选法的方案数。注意答案可能很大，请输出答案模1e9+7的结果。

核心思想

每次更新答案时判断一下，记录一个$cnt$数组，初始为1，表示背包容积为$i$时总价值为最佳的方案数，那么当$f$被更新时，$cnt_j$就会被更新成$cnt_{j-u}$，那么$cnt_j$加上$cnt_{j-u}$即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N=1e5+10;
const int mod=1e9+7;
int f[N];
int a[N],u[N],v[N];
int cnt[N];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=m;i++) cnt[i]=1;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&u[i],&v[i]);
        for(int j=m;j>=u[i];j--){
            if(f[j]<f[j-u[i]]+v[i]){
                f[j]=f[j-u[i]]+v[i];
                cnt[j]=cnt[j-u[i]];
            }
            else if(f[j]==f[j-u[i]]+v[i]) cnt[j]=(cnt[j]+cnt[j-u[i]])%mod;
        }
    }
    cout<<cnt[m];
}