算法基础之多重背包问题 II

发布时间:2023年12月24日

多重背包问题 II

  • 核心思想: 二进制优化

    • s拆成若干份可以表示s以内所有数字 (例如7 –> 1 2 4 可以表示出7以内所有数字)

    • 即转换成二进制拆出 然后将拆出的部分按照大小扩大 就成了01背包问题了

    •   #include<iostream>
        #include<cstring>
        #include<algorithm>
        #include<vector>
        
        using namespace std;
        const int N = 2010;
        
        int n,m;
        int f[N];
        
        struct Good{
            int v,w;
        };
        
        int main()
        {
            vector<Good> goods;
            cin>>n>>m;
            
            for(int i=0;i<n;i++)
            {
                int v,w,s;
                cin>>v>>w>>s;
                
                for(int k=1;k<=s;k*=2)  //二进制拆
                { 
                    s -= k;
                    goods.push_back({v*k,w*k});  //存入时 按照倍数扩大v和w
                }
                if(s>0) goods.push_back({s*v,s*w});  //扩大s倍存入
            }
            
            for(auto good : goods)   //01背包
            {
                for(int j=m;j>= good.v ;j--)
                {
                    f[j] = max(f[j] , f[j - good.v] + good.w);
                }
            }
            cout<<f[m];
        }
      
  • 不用结构体存 也可以用数组v[N],w[N]存

    • 边存边用cnt记录个数
文章来源:https://blog.csdn.net/Pisasama/article/details/135183078
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。