算法基础之完全背包问题

完全背包问题

• 核心思想：集合表示： f[i][j]表示前i种物品 总容量不超过j的最大价值

  • 求f[i][j]时 分为选0、1、2……n个第i种物品 n种情况

  • 每种情况为 f[i][j-kv] (取k个第i种物品)

    • 

  • 即f[i][j] = max(f[i-1][j] , f[i-1][j-v]+w,f[i-1][j-2v]+2w….f[i-1][j-kv]+kw);

    • 当求f[i][j-v]时 (f[i][j] 的之前求出来的) 表达式如下图②式
    • 因为j最多–kv是一定的 所以上下两式只相差一个w**(①式从第二项开始)**
    • 

  • 等效替代： f[i][j] = max(f[i-1][j] , f[i][j-v]);

    • 与01背包差别就是f[i][j-v] 也就是说优化一维数组时从小到大遍历即可

  •   #include<iostream>
      #include<cstring>
      #include<algorithm>
      
      using namespace std;
      const int N = 1010;
      
      int v[N],w[N];
      int f[N];
      int n,m;
      
      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++)
              {
                  f[j] = max(f[j] , f[j-v[i]]+w[i]);
            //f[i][j]=max(f[i-1][j],f[i][j-v[i]] + w[i])
              }
          }
          
          cout<<f[m];
      }