当前位置： 首页 > article >正文

背包问题总结

article 2024/11/18 9:34:03

01背包问题

  朴素版：

              f[i][j]在这里指从所有前i个物品中选且容积不超过j的所有选法中的最大价值，所以答案是f[n][m],即从前n件物品中选且总体积不超过m的所有选法中的最大价值，符合题意。注意只有枚举到的容积大于第i个物品的体积时(也就是j>=v[i]时)才要考虑要不要将第i个物品装进去。

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;//n代表物体个数，m代表背包容量
int f[1010][1010];
int v[1010],w[1010];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>v[i]>>w[i];//v[i]代表第i个物品的体积，w[i]代表第i个物品的价值
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(j>=v[i])//如果当前容积>=当前物品的体积才要考虑要不要把第i件物品装进去
            {
                f[i][j]=max( f[i-1][j] , f[i-1][j-v[i]]+w[i] );
            }
            else//如果容积不够第i件物品的体积根本不用考虑第i件物品
            {
                f[i][j]=f[i-1][j];
            }
        }
    }
    cout<<f[n][m];
    return 0;
}

优化版：

由状态计算方程：

可知：对于每一次的当前状态，都是由上一层(i-1)层转移过来，对应到一维的话也就是由未更新的状态转移过来的，且二维中的j都是由比它小的状态 ( j - v [ i ] ) 转移过来的对应在一维就应该从大到小枚举，从而保证当前的j的状态是由第i-1层状态转移过来的。

一维状态 f [ j ] 可以理解为容积不超过 j 的所有选法的最大价值，用遍历 i 的for循环来控制考虑前 i

个物品。在二维状态中如果当前容积小于第i个物品的体积就由f [ i-1 ] [ j ]转移过来，对应在一维中就是f[ j ]=f[ j ],当前状态由上一层的 j 转移过来，由于当前的 j 还没更新所以它此时就是上一层的状态所以就不用考虑了。

注意在更新 f [ j ] 状态时，要让 j 从大到小枚举且 j 的下限要>=v [ i ] ,这时候才会更新f[ j ] 。

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;//n代表物体个数，m代表背包容量
int f[1010];
int v[1010],w[1010];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>v[i]>>w[i];//v[i]代表第i个物品的体积，w[i]代表第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] );
        }
    }
    cout<<f[m];
    return 0;
}

注意答案是 f [ m ] 。 

补充版：

上面给出的是 f [ i ] [ j ] 表示从前i个物品中选且总体积不超过 j 的所有选法的最大价值。下面给出的是f [ i ] [ j ] 表示从前i个物品中选且总体积恰好等于 j 的所有选法的最大价值。

此时分析的状态计算方程与之前一样，代码略微有些变化。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;//n代表物体个数，m代表背包容量
int f[1010][1010];
int v[1010],w[1010];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>v[i]>>w[i];//v[i]代表第i个物品的体积，w[i]代表第i个物品的价值
    memset(f,-0x3f,sizeof f);
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(j>=v[i])//如果当前容积>=当前物品的体积才要考虑要不要把第i件物品装进去
            {
                f[i][j]=max( f[i-1][j] , f[i-1][j-v[i]]+w[i] );
            }
            else//如果容积不够第i件物品的体积根本不用考虑第i件物品
            {
                f[i][j]=f[i-1][j];
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    res=max(res,f[i][j]);
    cout<<res;
    return 0;
}

分析代码变化：

        memset(f,-0x3f,sizeof f);

        注意此时f [ i ] [ j ] 的含义改变了：从前 i 个物品中选且体积恰好为 j 的所有选法的最大价值。

在之前代码中f [ i ] [ j ] 的初始化一直就是0，但是在这里要改变，比如 f [ 0 ] [ 5 ] 代表选了0个物品体积恰好为5的所有选法的最大价值，这种情况明显是不合法的，不合法就给它设为负无穷。但是从0件物品中选体积恰好为0合法，说明一件也没有选，所以最大价值就是0，所以 f [ 0 ] [ 0 ] = 0 。

另外：memset函数包括在<cstring>头文件中。

        for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        res=max(res,f[i][j]);

        注意最后的答案要遍历所有情况选出最大值，答案不再是 f [ n ] [ m ] 。 我们要求的是价值最大，但是价值最大的时候不一定背包装满了，注意恰好这个意思，对于所有 f [ i ] [ m ] 来说都意味着体积恰好为m时的最大价值，它的意思时在所有选法中体积恰好等于m的最大价值。但是可能背包没有装满时的最大价值比装满时的最大价值还要大，所以要枚举。

 一维优化过后的代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
int f[1010];
int v[1010],w[1010];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>v[i]>>w[i];
    memset(f,-0x3f,sizeof f);
    f[0]=0;
    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] );
        }
    }
    int res=0;
    for(int i=0;i<=m;i++)
    res=max(res,f[i]);
    cout<<res;
    return 0;
}

一维优化过后的代码与上相同，也是要memset(f,-0x3f,sizeof f);并且结果要遍历背包体积的所有情况。

完全背包问题

朴素版：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int f[N][N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w;//第i个物品的体积和价值
        cin>>v>>w;
        for(int j=0;j<=m;j++)
        {
            if(j>=v)f[i][j]=max(f[i-1][j],f[i][j-v]+w);//如果可以考虑是否选择第i个物品
            else f[i][j]=f[i-1][j];//没法选择第i个物品
            
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

由状态计算公式可知完全背包问题不需要枚举物品个数，与物品个数管，也就是s无关，都由 f [ i ] [ j - v ] 代替了。f[i-1][j]是不选第i个物品的最大价值，f[i][j-v]+w的值是选第i个物品且从选1个到选到能选的最大数的所有选法的最大价值。由状态计算式子f[i][j]=max(f[i-1][j],f[i][j-v]+w);可知每次更新要么是靠上一层的 j 要么是靠这一层的 j-v 。说明用一维优化的时候这个 j 要从小到大枚举，因为在更新 j 的时候，用到了本层的比 j 小的状态，所以要先更新小的状态。下面是一维优化版

优化版：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int f[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w;//第i个物品的体积和价值
        cin>>v>>w;
        for(int j=v;j<=m;j++)
        f[j]=max(f[j],f[j-v]+w);
    }
    cout<<f[m]<<endl;
    return 0;
}

如果没法更新，那 f [ j ] = f[ j ] ;还是之前的状态，如果可以更新（也就是 j 大于等于第i个物品的体积）f [ j ] = f [ j - v ] + w 。结果是f[m] 。

补充版：

下面为 f [ i ] [ j ] 表示所有从前 i 个物品中选，且总体积恰好为 j 的普通的完全背包问题代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;//n代表物体个数，m代表背包容量
int f[1010][1010];
int v[1010],w[1010];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>v[i]>>w[i];//v[i]代表第i个物品的体积，w[i]代表第i个物品的价值
    memset(f,-0x3f,sizeof f);
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(j>=v[i])//如果当前容积>=当前物品的体积才要考虑要不要把第i件物品装进去
            {
                f[i][j]=max( f[i-1][j] , f[i-1][j-v[i]]+w[i] );
            }
            else//如果容积不够第i件物品的体积根本不用考虑第i件物品
            {
                f[i][j]=f[i-1][j];
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    res=max(res,f[i][j]);
    cout<<res;
    return 0;
}

下面为 f [ i ] [ j ] 表示所有从前 i 个物品中选，且总体积恰好为 j 的一维优化的完全背包问题代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
int f[N];
int n,m;
int main()
{
    cin>>n>>m;
    memset(f,-0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        int v,w;//第i个物品的体积和价值
        cin>>v>>w;
        for(int j=v;j<=m;j++)
        f[j]=max(f[j],f[j-v]+w);
    }
    int res=0;
    for(int i=0;i<=m;i++)
    res=max(res,f[i]);
    cout<<res;
    return 0;
}

多重背包问题：

朴素版：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int n,m;
int f[N][N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=s&&k*v<=j;k++)//第i件物品选k件
            f[i][j]=max(f[i][j],f[i-1][j-k*v]+k*w);
        }
    }
    cout<<f[n][m];
    return 0;
}

注意：多重背包问题是三重循环，先枚举物品种数，再枚举体积，最后枚举每件物品的件数。for(int k=0;k<=s&&k*v<=j;k++)//第i件物品选k件                                                                                  保证了要么k取到物品所提供的最大值s要么就是s件物品全选的话会超过 j 所及就选到不超过s且体积不超过 j 的最大 k 。

优化版：

        1.二进制优化

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2010;
int n,m;
int f[N];
int v[N],w[N],cnt=0;//存放每组打包好之后的体积和价值
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int a,b,s;//a代表当前物品体积，b代表当前物品价值,s代表当前物品件数
        cin>>a>>b>>s;
        int k=1;
        while(k<=s)
        {    
            cnt++;//打包一组
            v[cnt]=k*a;//将k件物品打包在一起，那么这一组体积就要对应这k件物品的体积之和
            w[cnt]=k*b;//将k件物品打包在一起，那么这一组价值就要对应这k件物品的价值之和
            s=s-k;//已经有k件物品打包好了，要减去
            k=k*2;
        }
        if(s)//如果除去二进制的分组还有剩余的也就是C
        {
            cnt++;
            v[cnt]=s*a;
            w[cnt]=s*b;
        }
    }
    //分好组之后的情况就是从第一件物品开始，前几个组都是第1种物品，第一件物品打包完了，接着几个组是第2种物品，以此类推
    //物品已经分好组，下面就是01背包问题(一维优化版)
    for(int i=1;i<=cnt;i++)//此时是对cnt个新物品进行01背包
    {
        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;
}

上面代码主要用到的是01背包问题，因此，如果是恰好情况的话与上面01背包问题一样。

2.滑动窗口优化

先上代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=20010;
int f[N],g[N],q[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        for(int r=0;r<v;r++)
        {
            int hh=0,tt=-1;
            memcpy(g,f,sizeof f);
            for(int k=r;k<=m;k=k+v)
            {
                if(hh<=tt&&q[hh]<k-s*v)hh++;
                if(hh<=tt)f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);
                while(hh<=tt&&g[q[tt]]-(q[tt]-r)/v*w<=g[k]-(k-r)/v*w)tt--;
                q[++tt]=k;
            }
        }
    }
    cout<<f[m];
    return 0;
}

1.( g的存在 )将 f [ ] [ ] 后面这个中括号的值对应到数轴下标上，数轴下标对应的值为f，优化为一维的话需要再用一个数组g来记录上一层的状态，f来存当前状态，因为采用滑动窗口优化的方式只能从小到大来枚举体积，但是又f[i][j]式子可以知道每次的f[i][j]都是在上一层且体积比当前小的体积状态中取最大值所以不能采用前面其他背包问题采用的一维优化方式，因此需要再来一个数组g。memcpy(g,f,sizeof f);这一步就实现了把所有更新好的状态放到g中，准备新的一轮的更新

2.（余数r从[0,v)的遍历）只有将所有可能的余数都遍历，才能遍历出所有的0到 m 体积之间所有取物品情况                                                                                                                                             比如：背包容积为13，当前物品体积为4，那么r就可以取0，1，2，3 。f[4] 可以选择一件，f[5]可以选择一件，f[6]可以选择一件，f[7]可以选择一件，从f[8]开始最大选两件，f[12]开始最大选3件。这都是由不同的余数 r 加上选的件数*一件的体积决定的。

3. 解释if(hh<=tt&&q[hh]<k-s*v)hh++;用来判断当前队头是否已经划出窗口，!!!注意是k-s*v，不是k-（s+1）*v因为s代表物品有s件但是滑动窗口的长度是s+1

4.解释if(hh<=tt)f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);（注意此时还没有将k下标对应的位置放到滑动窗口里）所以最大值要么是当前位置要么是它前面的的某个最大值再加上相对于当前位置的偏移量。

5.解释g[q[tt]]-(q[tt]-r)/v*w<=g[k]-(k-r)/v*w

如果成立说明当前元素比队尾元素更好，队尾元素永远不能用了，就出队，记得用上一层的来判断，判断的要是同一层，并且通过减相对于当前r的偏移量w来判断（减的效果相当于加，因为都是递减）

补充版：

上面的01背包问题相当于多重背包问题只不过是每件物品可选择的数量为1。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=20010;
int f[N],g[N],q[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int v,w,s;
        cin>>v>>w;//此处是唯一的修改
        s=1;
        for(int r=0;r<v;r++)
        {
            int hh=0,tt=-1;
            memcpy(g,f,sizeof f);
            for(int k=r;k<=m;k=k+v)
            {
                if(hh<=tt&&q[hh]<k-s*v)hh++;
                if(hh<=tt)f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);
                while(hh<=tt&&g[q[tt]]-(q[tt]-r)/v*w<=g[k]-(k-r)/v*w)tt--;
                q[++tt]=k;
            }
        }
    }
    cout<<f[m];
    return 0;
}

只需要把s设为1就可以解决01背包问题，01背包问题就是多重背包问题s=1的情况。

分组背包问题

朴素版：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int n,m;
int f[N][N];
int v[N][N],w[N][N],s[N];//s存储每一组的物品数量
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];//v存储第i组第j个物品的体积，w存储第i组第j个物品的价值
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];//不选第i组物品
            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];
    return 0;
}

类似于01背包问题，相当于在01背包问题里面加了一层选择物品的循环。

优化版：

与01背包问题的一维优化一样，体积的枚举也是从大到小，（这里是从m到0了，加了一个if判断语句）另外恰好就是的情况与01背包一样。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int n,m;
int f[N];
int v[N][N],w[N][N],s[N];//s存储每一组的物品数量
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];//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];
    return 0;
}

分组背包问题其实就相当于01背包问题，只不过加了个物品的选择。

总结：

分组背包问题依靠01背包问题，01背包问题是多重背包问题s=1的情况，多重背包是完全背包的特殊情况，多重背包的二进制优化依靠01背包问题。此外，在一维优化的时候，完全背包问题枚举体积时是从小到大枚举的，其他背包都是从大到小枚举的。


http://www.kler.cn/a/398509.html

相关文章：

  • ONLYOFFICE8.2版本测评，团队协作的办公软件
  • 【学习】HTTP
  • HBase压测 ycsb
  • 推荐15个2024最新精选wordpress模板
  • 如何编译 Cesium 源码
  • C++初阶——优先队列
  • SQL初步注入
  • 微服务day08
  • H3C NX30Pro刷机教程-2024-11-16
  • 《生成式 AI》课程 第3講 CODE TASK 任务2:角色扮演的机器人
  • 【HarmonyOS】Hdc server port XXXX has been used.Configure environment variable
  • C++创建型模式之原型模式
  • npm、yarn、pnpm 切换查看镜像源笔记
  • OceansGallerie趣味游戏：带领Web2用户无缝融入Web3世界
  • spring基础题笔记（1）
  • （长期更新）《零基础入门 ArcGIS(ArcMap) 》实验一（下）----空间数据的编辑与处理（超超超详细！！！）
  • 如何在 Ubuntu 上安装 RStudio IDE（R语言集成开发环境） ?
  • K8S创建云主机配置docker仓库
  • Spring Boot项目pom.xml文件详解
  • css初始化（二十三课）
  • Python3.11.9+selenium，选择证书用多线程+键盘enter解决
  • VuePress v2 快速搭建属于自己的个人博客网站
  • 华为开源自研AI框架昇思MindSpore应用案例：人体关键点检测模型Lite-HRNet
  • 卷积神经网络（CNN）对 CIFAR-10 数据集进行图像分类
  • C++中的适配器模式
  • Prometheus面试内容整理-Prometheus 的架构和工作原理