01背包

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

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

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

0 1 ： 每个物品只能选择 0 或者 1 次

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

• 朴素版本

  #include <iostream>
  #include <algorithm>

  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]; 
      // 注意 i 从1开始

      for (int i = 1; i <= n; i ++)
          for (int j = 1 ;j <= m; j ++) // 内循环 递增 j
          {
              f[i][j] = f[i - 1][j];   // 第i个物品不选
              if(j >= v[i])
                  f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);  // 选1次
          }

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

      return 0;
  }

• 空间优化
  我们可以看出当前的状态之和上一层的左边的列有关系。
  如果是从下到大遍历的话，所依赖的关系被更新，不能得出正确答案。所以要倒序遍历

  计算新的状态值时涉及到的其他状态值是旧值，没有更新过
  如果第二层循环依旧从小到大递增，那么新的状态值的下标比较大，其依赖的状态值下标比较小，所以已经被更新，不符合状态计算.
  所以选择从大到小递减循环，这样依赖的下标小的状态值未更新，还是旧值

#include <iostream>
#include <algorithm>

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 = m; j >= v[i]; j -- )  // 内循环 递减
              f[j] = max(f[j], f[j - v[i]] + w[i]);
      // 内循环递减，下标大的先更新，小的后更新；
      // 更新下标大的值时，涉及到的下标小的值还未更新，用的是旧值
      // 和朴素写法等价

      cout << f[m] << endl;

      return 0;
  }