美文网首页动态规划专题
多重背包Ⅰ,Ⅱ/分组背包

多重背包Ⅰ,Ⅱ/分组背包

作者: Tsukinousag | 来源:发表于2021-02-19 15:12 被阅读0次
    • 多重背包问题Ⅰ

    原题链接

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

    第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

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

    数据范围:

    0< N , V ≤100
    0< vi , wi , si ≤100

    //朴素版多重背包问题≈朴素版完全背包问题,只不过加了物品数量的限定条件
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N=110;
    
    int n,m;
    int s[N],w[N],v[N];
    int dp[N][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<=s[i]&&k*v[i]<=j;k++)
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
                }
            }
        }
        cout<<dp[n][m]<<endl;
        return 0;
    }
    

    • 多重背包问题Ⅱ

    原题链接

    数据范围:

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

    最主要的思想是二进制优化,把问题转化为01背包问题

            int k=1;
            while(k<=s)//类似于将s[i]=16,拆成一堆二进制后1 2 4 8 1,与体积,质量乘积打包成一份一份
            {
                cnt++;
                v[cnt]=a*k;
                w[cnt]=b*k;
                s-=k;
                k*=2;
            }
            //如果s[i]没用连续的二进制打包完
            if(s>0)
            {
                cnt++;
                v[cnt]=a*s;
                w[cnt]=b*s;
            }
    
        
        n=cnt;//这是新的物品数量
    
    

    优化成简短点的代码

    for(int i=0;i<n;i++)
    {
      for(int k=1;k<=s;k*=2)//多重背包二进制优化
       {
           for(int j=m;j>=k*v;j--)
                dp[j]=max(dp[j],dp[j-k*v]+k*w);
           s-=k;    
       }
    }
    
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    const int N=12010;
    
    int dp[N];
    int v[N],w[N];
    int n,m;
    
    int main()
    {
        cin>>n>>m;
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            int a,b,s;
            cin>>a>>b>>s;
            //对每个s[i]二进制打包
            int k=1;
            while(k<=s)//类似于将s[i]=16,拆成一堆二进制后1 2 4 8 1,与体积,质量乘积打包成一份一份
            {
                cnt++;
                v[cnt]=a*k;
                w[cnt]=b*k;
                s-=k;
                k*=2;
            }
            //如果s[i]没用连续的二进制打包完
            if(s>0)
            {
                cnt++;
                v[cnt]=a*s;
                w[cnt]=b*s;
            }
        }
        
        n=cnt;//这是新的物品数量
        //因为经过上述操作后,每个物品的数量都来变成了1,于是转变成01背包问题,O(nvlogs)
        for(int i=1;i<=n;i++)
            for(int j=m;j>=v[i];j--)
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
                
        cout<<dp[m]<<endl;
        return 0;
    }
    

    • 分组背包

    原题链接

    当前物品的类型去判断属于哪一类背包问题,做出第i号物品在该类背包模型下的最优决策

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N=1e3+10;
    
    int dp[N];
    int n,m;
    
    int main()
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            int v,w,s;
            cin>>v>>w>>s;
            if(s==0)//完全背包
            {
                for(int j=v;j<=m;j++)
                    dp[j]=max(dp[j],dp[j-v]+w);
            }
            else
            {
                if(s==-1)s=1;//01背包
                for(int k=1;k<=s;k*=2)//多重背包二进制优化
                {
                    for(int j=m;j>=k*v;j--)
                        dp[j]=max(dp[j],dp[j-k*v]+k*w);
                    s-=k;
                    
                }
                if(s)//剩余s去做01背包
                {
                    for(int j=m;j>=s*v;j--)
                    {
                        dp[j]=max(dp[j],dp[j-s*v]+s*w);
                    }
                }
            }
        }
        cout<<dp[m]<<endl;
        
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:多重背包Ⅰ,Ⅱ/分组背包

        本文链接:https://www.haomeiwen.com/subject/zwtaxltx.html