[动态规划](1)背包问题

01背包

引言:

[ 0 -1 背包 ] 是较为简单的动态规划问题,也是其余背包问题的基础

动态规划是不断决策求最优解的过程,[0 - 1背包]既是不断对第 i 个物品的做出决策,[0-1]正好代表选与不选的两种决定

模板题2. 01背包问题 - AcWing题库

image-20210705004508799

思维导图:

image-20210704150916538

思路:

  • 状态fi定义:前 i 个物品,背包容量 j 下的最优解(最大价值)

    • 当前状态依赖于之前的状态,可以理解蔚初始状态 f0=0 开始决策,有N件物品,则需要N次决策,每一次对第i件物品的决策,状态 fi 不断由之前的状态更新而来。
  • 当前背包容量不够( j < v [i] ) , 没得选,因次前 i 个物品最优解既为 前 i - 1 个物品最优解:fi = f i-1
  • 当前背包容量够,可以选,因此需要决策 选 与 不选 第 i 件物品:

    • 选:fi = fi-1] + w[i]
    • 不选:fi = fi - 1

代码:

#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];//体积以及价值
int f[N][N];//j 体积下 前 i 个物品的最大价值
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    //f[0][0-m]=0 由于全局变量不需要初始化
    //代表 在 0个体积下 所有的状态全为0

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            f[i][j] = f[i - 1][j];//通用最优解
            if (j >= v[i])//在背包体积能装下第 i 件物品时,则决策是否选择第i件物品
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;
    return 0;
}

优化:

image-20210705004543924

我们可以发现,其状态只与他的上一维有关系,那么我们就可以采用 [ 滚动数组 ] 的方式来对其进行优化

#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];//体积以及价值
int f[2 * N];//j 体积下 前 i 个物品的最大价值
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    //f[0][0-m]=0 由于全局变量不需要初始化
    //代表 在 0个体积下 所有的状态全为0

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= m; j++)
                f[j] = max([j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;
    return 0;
}

完全背包

完全背包在 01背包 的基础上 增加了 每件物品可以无限次使用的限制,我们则需要在01背包的基础上枚举 使用 k 件第 i 件物品的情况

模板题3. 完全背包问题 - AcWing题库

image-20210704124353124

思维导图:

产品功能清单.jpg

代码(三维)

//状态表示:f[i][j]:从前i个物品,背包容量为j的情况下,选取所有选法的最大值
//朴素版:枚举1-n个物品在0-m的容量挑选0-k个第i个物品
#include<iostream>
#include<cstring>
using namespace std;
#define N 1010
int n,m;//物品个数,背包容量限制
int f[N][N];//状态转移数组
int v[N],w[N];//物品体积,物品价值
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];//处理输入物品体积和价值

    for(int i=1;i<=n;i++)//枚举1-n个物品
        for(int j=0;j<=m;j++)//枚举0-m的背包容量
            for(int k=0;k*v[i]<=j;k++)//枚举0-k个物品,k 限制为 当前 k 个 i 物品体积 小于等于 j
                f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
                //状态方程取到:max(包含第k个物品的最大值)

    cout<<f[n][m]<<endl;


    return 0;
}

优化(时间二维)

我们列举以下更新次序的内部关系:

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
    //在 j 的容量下选取 i 个 物品 的最大价值
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-2*v]+2*w , .....)
    //在 j - vi 的容量下 选取第 i 个物品 的最大价值
由上两式,可得出如下递推关系:
                        f[i][j]=max(f[i,j-v]+w , f[i-1][j])
                            //逐渐添加第 i 个物品 选取最大值

我们可以通过上述方程之间的关系发现:

  • 在 容量 为 j 的条件下找 最大价值的方案,更新到 容量 j 的时候,j - v 体积时最大的方案已经存在了
  • 所以只需要对比 j 体积的第一个方案和 j - v 体积的最大方案 + w 哪个大就可以了

总结来说:就是在 容量 大于 v[ i ] 的情况下 去试着 加入一个 [ 第 i 个物品 ] 看是否会比原有的大

//三维优化成二维:我们没必要枚举每一个k取到最大值,而是可以通过当前状态不断添加k个i物品来更新最大值
#include<iostream>
using namespace std;
#define N 1010
int n,m;
int f[N][N];
int v[N],w[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++){//枚举0-m的背包容量
            f[i][j]=f[i-1][j];//选0个第i个物品(不选第i个物品
            if(j>=v[i])//每当j能装得下第i个物品的时候,尝试添加一个第i件物品
                f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
        }

    cout<<f[n][m]<<endl;
    return 0;
}

优化(空间一维)

同样,上述代码也可用 01 背包 的思路优化,能用 滚动数组 来进行优化,需要注意的是 由于是 二维的状态是在 [ 前 i 个物品 ] 中进行枚举,其状态也是由当前 第 i 个 物品 中的集合 转移过来的,是由所以不用逆序

//可以利用滚动数组来优化空间 
#include<iostream>
using namespace std;
#define N 1010
int n,m;
int v[N],w[N];
int f[N];
int main(){
    cin>>n>>m;

    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<=m;j++)//与01背包不同的是更新状态用的是当前的状态,所以需要从小到大枚举
            f[j]=max(f[j],f[j-v[i]]+w[i]);//删去一维对方程作等价变形


    cout<<f[m]<<endl;

    return 0;
}

多重背包

多重背包问题增加了物品数量的限制,每种物品只能用 s 件,其思路跟完全背包很像

4. 多重背包问题 I - AcWing题库

image-20210704235016490

思维导图:

https://nullcode.fun/admin/write-post.php?cid=150###

代码

//多重背包朴素版本和完全背包近乎一致
//枚举每一种物品的不同数量即可
#include<iostream>
using namespace std;
#define N 1010
int n,m;
int f[N][N];
int v[N],w[N],s[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i]>>s[i];

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k*v[i]<=j&&k<=s[i];k++)
                f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);

    cout<<f[n][m]<<endl;
    return 0;
}

5. 多重背包问题 II - AcWing题库

由于每组物品的数量都不同,所以是不能采用完全背包的优化方式,则我们可以使用二进制对其进行优化,将每组物品的数量拆分出来,用01背包的思路既能解决

假设有一组商品,一共有11个,我们知道,十进制数字11可以这样表示

11 = 1011(B) = 0111(B) + (11 - 0111(B)) = 0111(B) + 0100(B)

朴素做法中,我们要求出含这组商品的最优解,我们要枚举11次( 枚举),现在如果我们把这组商品分别打包成含商品个数为1个,2个,4个,4个(分别对应0001,0010,0100,0100)的四个"新的商品",将问题转化为01背包问题,对于每个商品,我们都只枚举一次,那么我们只需要枚举四次,就可以找出这11中商品的最优解,这样就大大减少了枚举次数

这种优化对于大数的效果极为明显,例如有1024个商品,在正常情况下要枚举1025次,优化后转换为01背包只需要10次

//多重背包采用二进制方法优化,不用枚举1-s[i]的每一个数,而是将这些数字拆分为logs[i]个数
//例如:200=1+2+4+8+16+32+64 + 73(除73外其余全是2的整次幂,这些数字能组成1-200任何数)
#include<iostream>
using namespace std;
#define N 2010000
int n,m;
int f[N];
int v[N],w[N];
int main(){
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i++){
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;//从一件物品开始分割
        while(k<=s){//分割物品
            cnt++;//新的物品数量
            v[cnt]=a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2;
        }
        if(s>0){
            cnt++;
            v[cnt]=a*s;
            w[cnt]=b*s;
        }
    }
    //将所有物品分割完毕后 采用01背包即可
    n=cnt;
    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]);


    cout<<f[m]<<endl;
    return 0;
}

分组背包问题

模板题:9. 分组背包问题 - AcWing题库

分组背包问题将 物品 从 个体 变为了 一组 ,且每组只能选一个物品 例如 水果这一组 选了苹果就不能选 西瓜

image-20210705003311528

思维导图:

image-20210705004052667

代码

#include<iostream>
#include<algorithm>
using namespace std;
#define N 10010
int n,m;
int f[N][N],v[N][N],w[N][N],s[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=1;j<=s[i];j++)
            cin>>v[i][j]>>w[i][j];
    }

    for(int i=1;i<=n;i++)//枚举n种
        for(int j=0;j<=m;j++){//枚举背包容量
            f[i][j]=f[i-1][j];
            for(int k=1;k<=s[i];k++){//枚举组内每一种物品
                if(j>=v[i][k])
                f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);//每组每个物品只能选一种,即上一组物品的状态加价值(背包减去容量)
            }
        }

    cout<<f[n][m]<<endl;
    return 0;
}
*/
//优化空间版本,可用滚动数组优化
#include<iostream>
using namespace std;
#define N 1100
int n,m;
int f[N],v[N][N],w[N][N],s[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=1;j<=s[i];j++)
            cin>>v[i][j]>>w[i][j];
    }

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

    cout<<f[m]<<endl;
    return 0;
}

本文链接:

https://nullcode.fun/150.html
1 + 2 =
快来做第一个评论的人吧~