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

多重背包问题 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记录个数