完全背包

集合 ：  用前i个物品 ，装进体积为j 的所有方案的集合  f[i][j]

属性 ：  所选方案中物品价值的最大值

计算 | 集合的划分 ： 第i个物品选择次数来划分 

完全 ：  每个物品可以选择无数次，但是不能超过背包的体积

三重循环 -> 二重循环 时间优化
二维数组 -> 一维数组 空间优化

• 朴素写法一

      #include <iostream>

      using namespace std;

      const int N = 1010;

      int n, m;
      int v[N], w[N];
      int f[N][N];

      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 = 1; j <= m; j ++ )
              {
                 f[i][j] = f[i - 1][j];  // 第i个物品选0次
                 for(int k = 1; k <= j / v[i]; k ++)
                  { 
                     f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); // 选k次
                  } 
              }


          cout << f[n][m] << endl;

          return 0;
      }

• 朴素写法二

      #include <iostream>

      using namespace std;

      const int N = 1010;

      int n, m;
      int v[N], w[N];
      int f[N][N];

      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 = 1; j <= m; j ++ )
              {
                  f[i][j] = f[i - 1][j];             // 第i个物品选0次
                  if (j >= v[i]) 
                      f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]); //  第i个物品选其他次
                   //针对朴素写法1 的f[i][j] 的等价变换 f[i][j-v]推导得出
              }

          cout << f[n][m] << endl;

          return 0;
      }

• 空间优化

      #include <iostream>

      using namespace std;

      const int N = 1010;

      int n, m;
      int v[N], w[N];
      int f[N];

      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 ++ )  // 注意j的初值
                  f[j] = max(f[j], f[j - v[i]] + w[i]);
          // 内循环递增  
          // 恒等式 f[j] = f[j]省略没写 ; if(j >= V[i])的条件判断 直接写到for里面 
          cout << f[m] << endl;

          return 0;
      }