背包DP

HYLW · 2023-10-10 15:00:53 · 算法·理论

返回母本《动态规划》

动态规划常用模型——背包问题：

给定一组物品，每种物品都有自己的重量和价格，在限定的总重量和一定选择规则内，我们如何选择，才能使得物品的总价格最高。

1.01背包问题

问题描述：

给定一个容量为 v 的背包、一组 n 个各有不同价值 w_i 、不同体积 v_i 的物品，将若干物品放入背包，每件物品至多用一次，如何选择，使得背包中物品总价值最大。求最大价值。

输入格式

第一行两个整数，N,V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000,0<vi,wi≤1000

输入样例

输出样例：

解：

我们设 f(i,j)(0\leq i,j) 表示在选择前 i 个物品、使用最大体积为 j 的选法中最大价值选法的所得价值，

（此时，“集合”：选择前 i 个物品、使用最大体积为 j 的选法；“属性”：最大价值）

对于计算 f(i,j) ,由01背包问题的定义可知，对于当前物品，只有“选”与“不选”两种状态，

“不选”：从前 i-1 个物品、使用最大体积为 j 的选法中最大价值选法的所得价值，即 f(i-1,j)；

“选”:显然，选了当前物品后，体积为 j-v_i ，则在选当前物品前，状态 f(i-1,j-v_i) ，在加上当前物品，即 f(i-1,j-v_i)+w_i 。

得状态转移方程：

f(i,j)=\max(f(i-1,j),f(i-1,j-v_i)+w_i)

代码1.0：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;

int n,m;//物品数量、背包容积 
int v[N],w[N];//物品体积、物品价值 
int f[N][N];//状态或答案 

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);
    //朴实输入
    //f[0][0~m]=0
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];//不选
            if(j>=v[i])//选，前提是装得下 
                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); 
        }

    printf("%d",f[n][m]); 
    return 0;
}

代码优化2.0：

可以发现，无论是代码还是方程中，f(i,j) 或 f[i][j] 中 i 这一层在每次更新中只用到了 i 与 i-1 ，此时可以想到可以用滚动数组来优化空间；

然而还发现，在代码和方程中，j-v_i,j\leq j ，所以结合上述结论，可以有二维转为一维。

还有一个问题是，在原代码中是从体积小到体积大来“规划”，事实上前一个 f 的改变会影响后一个 f 的规划，所以要倒着规划。

#include<bits/stdc++.h>
using namespace std;
const int N=1010;

int n,m;//物品数量、背包容积 
int v[N],w[N];//物品体积、物品价值 
int f[N];//状态或答案 

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);
    //朴实输入
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)//倒着规划 
            f[j]=max(f[j],f[j-v[i]]+w[i]); 
            //不选;选，前提是装得下 
    printf("%d",f[m]); 
    return 0;
}

其实，抛开背包问题本身来讲，以线性DP的视角来看，

所谓的“体积”是一个限制元素，而“价值”是一个目标元素

，这样理解，有助于做题时的阅读理解。

练习
luogu P1048 [NOIP2005 普及组] 采药
luogu P2871 [USACO07DEC] Charm Bracelet S
luogu P1060 [NOIP2006 普及组] 开心的金明attention：简单的转化
luogu P1049 [NOIP2001 普及组] 装箱问题attention：貌似题目中并没有价值，但一般来讲，目标元素即为“价值”，限制元素为“体积”，所以，你的结论是？
luogu P2639 [USACO09OCT] Bessie's Weight Problem Gattention：你做过，不是吗？同时，二倍经验。
AcWing 278.数字组合attention：出现了一个DP核心的重大转变，好好消化。

2.完全背包问题

问题描述：给定一个容量为 v 的背包、一组 n 个各有不同价值 w_i 、不同体积 v_i 的物品，将若干物品放入背包，每件物品可以有无数个，如何选择，使得背包中物品总价值最大。求最大价值。

例题：

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 v_i ，价值是 w_i 。

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

输入格式

第一行两个整数，N,V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000,0<vi,wi≤1000

输入样例

输出样例：

解：

与01背包类似地，只是在取个数上多了一维，你以为有无限个，实际上拿走的 k 个满足 v_j\times k\leq j,k\in Z ,得

初代代码(朴素)：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;

int n,m;//物品数量、背包容积 
int v[N],w[N];//物品体积、物品价值 
int f[N][N];//状态或答案 

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);
    //朴实输入

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int z=1;z*v[i]<=j;z++)//实际上个数满足vi*k<=j 
                f[i][j]=max(f[i-1][j],f[i-1][j-z*v[i]]+z*w[i]); 

    printf("%d",f[n][m]); 
    return 0;
}

代码优化2.0：

显然，有着与01背包类似的优化方向，但此时只优化了空间，时间复杂度仍然不够优秀。

观察方程

f(i,j)=\max(f(i-1,j),f(i-1,j-v_i)+w_i,f(i-1,j-2v_i)+2w_i,......)

f(i,j-v_i)=\max(f(i-1,j-v_i),f(i-1,j-2v_i)+w_i,f(i-1,j-3v_i)+2w_i,......)

发现

f(i,j)=\max(f(i-1,j),f(i,j-v_i)+w)

得到全新的状态转移方程，再加上空间降维

#include<bits/stdc++.h>
using namespace std;
const int N=1010;

int n,m;//物品数量、背包容积 
int v[N],w[N];//物品体积、物品价值 
int f[N];//状态或答案 

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&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]); 
        }

    printf("%d",f[m]); 
    return 0;
}

练习
AcWing 1023,买书attention：涉及一个DP核心的转变，好好消化
luogu P5020 [NOIP2018 提高组] 货币系统attention：这是一道综合性很高的题，首先你得做阅读理解，其次你得有一个转化方向，最后严谨地证明你的结论（~~当然你可以赌你是对的~~），还有一点是它涉及到DP核心的一个转变，最后，玩儿得开心《蒟蒻作者的代码及思路》

3.多重背包问题

问题描述：给定一个容量为 v 的背包、一组 n 个各有不同价值 w_i 、不同体积 v_i 的物品，将若干物品放入背包，每件物品有固定的个数 s_i，拿物品时不超过各自个数，如何选择，使得背包中物品总价值最大。求最大价值。

例题：

有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 s_i 件，每件体积是 v-i ，价值是 w-i 。

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

输入格式

第一行两个整数，N,V ，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 v_i,w_i,s_i ，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤100,0<v_i,w_i,s_i≤100

输入样例

输出样例：

解：

显然，它与完全背包问题非常相似，我们可以很容易的得到初始的状态转移方程：

f[i,j]=\max(\{f[i-1,j-v[i]\cdot k]+k\cdot w[i]\})(i\in [0,N],k\in [0,s[i]])

此时我们当然可以用朴素方法直接写：

初代代码：

#include<bits/stdc++.h>
using namespace std;
const int N=110;

int n,m;//物品数量、背包容积 
int v[N],w[N],s[N];//物品体积、物品价值 
int f[N][N];//状态或答案 

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&v[i],&w[i],&s[i]);
    //朴实输入

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int z=0;z*v[i]<=j && z<=s[i];z++)//实际上个数满足vi*k<=j 
                f[i][j]=max(f[i][j],f[i-1][j-z*v[i]]+z*w[i]); 

    printf("%d",f[n][m]); 
    return 0;
}

显然，三重循环太危险了，当限制范围过大时，容易超时，并且空间上也不理想。

如何优化？

显然，多重背包问题的个数是确定的，完全背包问题虽然类似，但两者的性质上有巨大不同，即后者的个数是动态的，不确定的。

其次，我们试着像完全背包问题一样去优化：

f[i,j]=\max(f[i-1,j],f[i-1,j-v[i]]+w[i],f[i-1,j-2v[i]]+2w[i] ……f[i-1,j-s[i]v[i]]+s[i]w[i]) f[i,j-v[i]]=\max(f[i-1,j-v[i]],f[i-1,j-2v[i]]+w[i],f[i-1,j-3v[i]]+2w[i],……,f[i-1,j-(s[i]+1)v[i]]+(s[i]+1)w[i])

可以看到，f[i,j-v[i]] 的后面多了一项，我们并不能像优化完全背包问题一样去优化它。

其实，由于物品的个数确定，所以多重背包问题更像01背包问题，我们当然可以把 s_i 个同种物品看成 s_i 个“不同”而价值、体积相同的物品。

但这并没有达到优化的目的。

联想一下人民币，你只有面值为$1,2,5$元的纸币，但是你可以通过组合凑出所有你想要的价值，这就是**值的一种集成化**，**集成化程度越高，组合方案越简单**（例如，10个10和2个50，这里的“简单”是指组合元素个数、种类相对较少），在集成化既需要高度有需要全面性的时候，我们不妨想到数的表示，二进制表示是种很好的方法。可知，任何数都可以表示为： >$x=2^0\cdot a_0+2^1\cdot a_1+2^2\cdot a_2……+2^k\cdot a_k(a_k\in \{0,1\})

那么，对于任何的 s_i 个同种物品来讲，把他们分成 1,2,4,8,16,…… 个集成的新物品，就可以通过组合来表示有小于 s_i 的数，具体来讲，

$1,2,4$可以表示 $0$~$7$的所有数，以此类推，$1,2,4,8,……2^k$ 就、可以表示 $0$~$\sum\limits_{i=0}^{k}2^i$ 的所有数当需要表示 $0$~$5$的所有数时，只需要$1,2,2$ 即可，那么，以此类推，对于任意 $s_i$ 来讲，把它分解为 $1,2,4,……$ 直到它们的和小于 $s_i$的第一个数，再加上它们和与 $s_i$ 的差，就可以表示 $0$~$s_i$ 的所有数。在如此**二进制优化**后，时间复杂度 $O(N\cdot V\cdot log_2s_{max})_{\max} \thickapprox O(2\times10^7)

理论可行，实践开始。

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int n,V;
int v[N],w[N],cnt=0,f[N];
int main(){
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++){
        int a,b,s;
        scanf("%d%d%d",&a,&b,&s);
        //集成化开始 
        int j=1;
        while(j<=s){//有可能刚好够 
            cnt++;
            v[cnt]=j*a;
            w[cnt]=j*b;
            s-=j;
            j*=2;//倍增 
        }
        if(s>0){//还有剩 
            cnt++;
            v[cnt]=s*a;
            w[cnt]=s*b;
        }
    }

    n=cnt;

    for(int i=1;i<=n;i++)
        for(int j=V;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);//01背包问题 

    printf("%d",f[V]);
    return 0;
}

但是，当 s_i 特别大时，时间复杂度仍然不合格，所以我们需要一种 O(1) 的做法来得到 \max(f[i-1,j],f[i-1,j-v_i]+w_i,f[i-1,j-2v_i]+2w_i……f[i-1,j-s_iv_i]+s_iw_i) 。

一点想法是，可以注意到，s_i 是固定的，随着 j 在枚举中增长，对于上述目标来讲，它的范围即 [j-s_iv_i,j] 也是增长的，并且长度不变，这是一种典型的模型。

还记得滑动窗口吗？

那么，这种优化的详解在这儿。~~蒟蒻不会写~~

4.分组背包问题

问题描述：给定一个容量为 v 的背包、 N 组 n 个各有不同价值 w_i 、不同体积 v_i 的物品，从各组中只拿一个物品放入背包，如何选择，使得背包中物品总价值最大。求最大价值。

例题：

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

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

输出最大价值。

输入格式

第一行有两个整数 N,V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N 组数据：

每组数据第一行有一个整数 S_i，表示第 i 个物品组的物品数量；
每组数据接下来有 S_i 行，每行有两个整数 v_{ij},w_{ij}，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤100,0<S_i≤100,0<v_{ij},w_{ij}≤100

输入样例

输出样例：

解：

其实，这跟01背包没啥区别。

代码：


#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int s[N],v[N][N],w[N][N];
int f[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        for(int j=1;j<=s[i];j++)
            scanf("%d%d",&v[i][j],&w[i][j]);

    }

    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--){
            for(int z=1;z<=s[i];z++){
                if(j-v[i][z]>=0)
                    f[j]=max(f[j],f[j-v[i][z]]+w[i][z]);
            }
        }

    printf("%d",f[m]);
    return 0;
}

练习：
P1757 通天之分组背包
P5322 [BJOI2019] 排兵布阵attenton：阅读理解，技巧性优化，思维与创新。《蒟蒻作者的代码与解析》
AcWing 1074.苹果二叉树

可以先到背包训练场练习

5.二维费用背包问题

“二维”

是指对于“限制元素”而言的二维化，当然，二维费用背包问题也包含了上述的01背包、完全背包、多重背包。

二维费用背包问题并不难，接下来，以01背包为例来了解一下。

例题：

题目描述

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M 。

每件物品只能用一次。体积是 v_i ，重量是 m_i ，价值是 w_i 。

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

输出最大价值。

输入格式

第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 N 行，每行三个整数 v_i,m_i,w_i，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N≤1000

0<V,M≤100

0<vi,mi≤100

0<wi≤1000

输入样例

输出样例：

解：

看图示理解。~~蒟蒻不会？懒得写~逃~~

当然，优化降维不在话下，同时也要倒序循环。

noding:

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

int n,V,M;
int f[110][110];

int main(){
    scanf("%d%d%d",&n,&V,&M);
    for(int i=1;i<=n;i++){
        int v,m,w;
        scanf("%d%d%d",&v,&m,&w);
        for(int j=V;j>=v;j--)
            for(int k=M;k>=m;k--)
                f[j][k]=max(f[j][k],f[j-v][k-m]+w);
    }
    printf("%d",f[V][M]);
    return 0;
}

练习：
AcWing 1022.宠物小精灵之收服
AcWing 1020.潜水员attention：这里将出现两个特别大的转变，事关DP核心，这个问题难而不难，且很重要，好好消化

6.背包问题求具体方案

相信你一定听说过，有的时候我们可以

……把动态规划中的每个状态看做点，状态间的关系就是有向边，此时动态规划具体化演变成一个有向图……

那么，背包问题更可以说明这个问题

01背包的初态方程：f[i][j]=\max(f[i-1][j],f[i-1][j-v[i]]+w[i])

那么，常规的背包问题（一维限制，属性MAX，集合“不超过”）可以看成最长路，此时的具体方案，就是最长路的路径。

记录一下就可以了，两种方式：

在动规后，从答案开始，判断转移状态间的相等关系，以此“顺藤摸瓜”。（\textcolor{blue}{\textbf{费时间}}）

在动规时，作对应状态的记录，最后反序查看。（\textcolor{orange}{{\textbf{又费时间又费空间}}}）

蛋疼的一点是，求具体方案时无法降维优化。

例题
解

这题唯一的麻烦事是输出字典序最小的方案，

但也不麻烦，由于在找路径时我们是倒序查找，那么在动规时我们倒序规划，令查路径正序即可。

这里就只展示第一种方式。

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

const int N = 1010;

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

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&v[i],&w[i]);

    for(int i=n;i>=1;i--)
        for(int j=0;j<=m;j++){
            f[i][j]=f[i+1][j];
            if(j>=v[i])
                f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
        }
    //此时答案变成f[1][m]
    int k=m; 
    for(int i=1;i<=n;i++)
        if(k>=v[i] && f[i][k]==f[i+1][k-v[i]]+w[i]){
            printf("%d ",i);
            k-=v[i];
        }
    return 0;
}

练习
P2066 机器分配attention：注意阅读理解，利用所学《蒟蒻作者的代码及解析》

7.背包问题求最优方案数

特殊的方案数求解。

例题
解：

其实这一点应和上一点合并，因为他们的理解相同，那么利用上面的思想，对应每个状态设置一个记录表示最优值下的方案数，在转移（或说计算）时，若最优值相等则方案数加一，同时在转移时方案数根据“来路”更新。

具体地，看代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;
int f[N],cnt[N];
int main()
{
    int n,m;
    cin>>n>>m;
    cnt[0]=1;
    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        {
            if(f[j-v]+w>f[j])
            {
                f[j]=f[j-v]+w;
                cnt[j]=cnt[j-v];
            }
            else if(f[j-v]+w==f[j]) cnt[j]=(cnt[j]+cnt[j-v])%mod;
        }
    }
    int ans=0;
    for(int i=0;i<=m;i++)
    {
        if(f[i]==f[m])ans=(ans+cnt[i])%mod;
    }
    cout<<ans;
    return 0;
}

背包DP

返回母本《动态规划》

动态规划常用模型——背包问题：

1.01背包问题

问题描述：

输入格式

输出格式

数据范围

输入样例

输出样例：

解：

代码1.0：

代码优化2.0：

练习

2.完全背包问题

例题：

输入格式

输出格式

数据范围

输入样例

输出样例：

解：

初代代码(朴素)：

代码优化2.0：

练习

3.多重背包问题

例题：

输入格式

输出格式

数据范围

输入样例

输出样例：

解：

初代代码：

4.分组背包问题

例题：

输入格式

输出格式

数据范围

输入样例

输出样例：

解：

练习：

可以先到背包训练场练习

5.二维费用背包问题

“二维”

题目描述

输入格式

输出格式

数据范围

输入样例

输出样例：

解：

noding:

练习：

6.背包问题求具体方案

例题

解

练习

7.背包问题求最优方案数

例题

解：

返回母本《动态规划》