01背包问题

大家觉得好的话，点点赞呗，哈哈哈！

特点： 每件物品仅用一次

N件物品，容量为V的背包。每件物品只能用一次。

将fi表示的所有选法分成两大类（划分原则：不漏）

① 选法中不含 i ， 即从 1 ~ i-1中选，且总体积不超过j，即 f[i-1]

② 选法中包含 i ，即从 1 ~ i 中选，包含 i，且总体积不超过 j

可以先把第 i 个物品拿出来，即从第 1 ~ i-1中选，且总体积不超过 j-v[i]

即：f[i-1][j-v[i]] + w[i];

所以：f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]);

例子：

总共：
4件物品 背包容量为5
体积  价值
 1     2
 2     4
 3     4
 4     5
 则应该选，中间两样东西，体积之和为5，价值之和为8

朴素做法：

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N], w[N];
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    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];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }

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

从二维优化成一维（空间优化）

如果直接删除掉 f[i] 这一维即

f[j] = max(f[j], f[j-v[i]] + w[i]);

如果删掉f[i]这一维，结果如下：（如果j层循环时递增的，则是错误的）
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]);
    }
}

证明：j层循环是递增的，则是错误的

原式：f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);

改成一维：f[j] = max(f[j], f[j - v[i]] + w[i]);

由于 f[i][] 只跟上一状态（f[i - 1][]）有关 上面两个式子 ：这一状态（左） = 上一状态（右）

即 f[i][j] 是由 f[i - 1][j - v[i]] 推出来的 现在进行空间优化，那么必须要保证 f[j] 要由 f[j - v[i]] 推出来的。

如果j层循环是递增的，则相当于 f[i][j] 变得是由 f[i][j - v[i]] 推出来的， 而不是 f[i - 1][j - v[i]] 推出来的。

例子：假设有3件物品，背包的总体积为10

   物品    体积     价值 
  i = 1     4       5  
  i = 2     5       6  
  i = 3     6       7  

因为 f[0][j] 总共0件物品，所以最大价值为 0， 即 f[0][j] == 0 成立

    如果 j 层循环是递增的： 
    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[0] = 0;  f[1] = 0;  f[2] = 0;  f[3] = 0;  f[4] = 0;  
    f[5] = 0;  f[6] = 0;  f[7] = 0;  f[8] = 0;  f[9] = 0; f[10] = 0;
    当进入循环 i == 1 时：
    f[4] = max(f[4], f[0] + 5); 即max(0, 5) = 5; 即f[4] = 5;
    f[5] = max(f[5], f[1] + 5); 即max(0, 5) = 5; 即f[5] = 5;
    f[6] = max(f[6], f[2] + 5); 即max(0, 5) = 5; 即f[6] = 5;
    f[7] = max(f[7], f[3] + 5); 即max(0, 5) = 5; 即f[7] = 5;
    重点来了！！！
    f[8] = max(f[8], f[4] + 5); 即max(0, 5 + 5) = 10; 即f[8] = 10;
    这里就已经出错了
    因为此时处于 i == 1 这一层，即物品只有一件，不存在单件物品满足价值为10
    所以已经出错了。

    如果 j 层循环是逆序的：
    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]);
        }
    }

模拟过程如下：

    当还未进入循环时:
    f[0] = 0;  f[1] = 0;  f[2] = 0;  f[3] = 0;  f[4] = 0;  
    f[5] = 0;  f[6] = 0;  f[7] = 0;  f[8] = 0;  f[9] = 0; f[10] = 0;
    当进入循环 i == 1 时：w[i] = 5; v[i] = 4;
    j = 10：f[10] = max(f[10], f[6] + 5); 即max(0, 5) = 5; 即f[10] = 5;
    j = 9 ：f[9] = max(f[9], f[5] + 5); 即max(0, 5) = 5; 即f[9] = 5;
    j = 8 ：f[8] = max(f[8], f[4] + 5); 即max(0, 5) = 5; 即f[8] = 5;
    j = 7 ：f[7] = max(f[7], f[3] + 5); 即max(0, 5) = 5; 即f[7] = 5;
    j = 6 ：f[6] = max(f[6], f[2] + 5); 即max(0, 5) = 5; 即f[6] = 5;
    j = 5 ：f[5] = max(f[5], f[1] + 5); 即max(0, 5) = 5; 即f[5] = 5;
    j = 4 ：f[6] = max(f[4], f[0] + 5); 即max(0, 5) = 5; 即f[4] = 5;
    当进入循环 i == 2 时：w[i] = 6; v[i] = 5; 
    j = 10：f[10] = max(f[10], f[5] + 6); 即max(5, 11) = 11; 即f[10] = 11;
    j = 9 ：f[9] = max(f[9], f[4] + 6); 即max(5, 11) = 5; 即f[9] = 11;
    j = 8 ：f[8] = max(f[8], f[3] + 6); 即max(5, 6) = 6; 即f[8] = 6;
    j = 7 ：f[7] = max(f[7], f[2] + 6); 即max(5, 6) = 6; 即f[7] = 6;
    j = 6 ：f[6] = max(f[6], f[1] + 6); 即max(5, 6) = 6; 即f[6] = 6;
    j = 5 ：f[5] = max(f[5], f[0] + 6); 即max(5, 6) = 6; 即f[5] = 6;
    当进入循环 i == 3 时: w[i] = 7; v[i] = 6; 
    j = 10：f[10] = max(f[10], f[4] + 7); 即max(11, 12) = 12; 即f[10] = 12;
    j = 9 ：f[9] = max(f[9], f[3] + 6); 即max(11, 6) = 11; 即f[9] = 11;
    j = 8 ：f[8] = max(f[8], f[2] + 6); 即max(6, 6) = 6; 即f[8] = 6;
    j = 7 ：f[7] = max(f[7], f[1] + 6); 即max(6, 6) = 6; 即f[7] = 6;
    j = 6 ：f[6] = max(f[6], f[0] + 6); 即max(6, 6) = 6; 即f[6] = 6;

就模拟一下发现没有错误，即逆序就可以解决这个优化的问题了

优化后的代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N];
int v[N], w[N];
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    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;
}

大家觉得好的话，点点赞呗，哈哈哈！