什么是01背包？
要么是0不选，1选的，且每种只有一个能选放进背包的背包问题。

比如，背包容量V=5,
下面四个
volume weight(value)
1 2
2 4
3 4
4 5

我们关心就两个互相关联的值，V价值和W重量(volume体积容量)
所以不妨设一个二维数组来定义状态。定义这个集合，和统计里的样本空间类似。Ω = {背包能放下的元素}
根据题意，定义f[i][j]为选完第i个物品，j为背包体积时的最大价值。
为什么要这么定义呢？
因为分析背包时，不难想出来只要每个物品判断一次选或不选，就可以足以推理出最终的价值。
所以，使用i这个维度来定义每个物品。
而题意要价值，而价值和体积强关联,仅受体积约束，所以i需要关联j。f[i][j]. QED.

剩下的就把corner case判断下码完就完事了

#include<iostream>
using namespace std;
const int N = 1010;
int v[N],w[N];
int f[N][N];
int main(){ //才不是go的坏习惯
    int n, V;
    cin >> n >> V;
    for (int i = 1; i<=n;i++){
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i<=n;i++){
        for (int j = 0; j <= V; j++){
            if (j >= v[i]){
                f[i][j]=max(f[i - 1][j-v[i]]+w[i],f[i-1][j]);
            } else{
                f[i][j] = f[i - 1][j];//背包放不下当前巨物就不选
            }
        }
    }
    cout << f[n][V] << endl;
    return 0;
}

逻辑就分析到这就结束了。

剩下就是奇淫怪技了
由于i维度,只依赖i-1, 很明显可以用递推，按背包容量按顺序装.

然而，这种优化需要一个特殊的技巧：我们需要从大到小遍历背包容量 j。原因如下：

• 如果我们从小到大遍历 j，那么在计算 f[j] 时，f[j-v[i]] 实际上已经被更新为了 i 轮的值，这是不正确的，因为我们需要的是 i-1 轮的 f[j-v[i]]。

• 如果我们从大到小遍历 j，那么在计算 f[j] 时，f[j-v[i]] 还没有被更新，仍然是 i-1 轮的值，这是正确的。

#include<iostream>
using namespace std;
const int N = 1010;
int v,w;
int f[N];
int main(){ //才不是go的坏习惯
    int n, V;
    cin >> n >> V;
    for (int i = 1; i<=n;i++){ //关键在于这个i轮循环。 对于j从小到大遍历，f[j-v]比f[j]先计算，所以f[j-v]等价于f[i][j-v]。所以这里j背包要从大到小遍历。这样f[j-v]后计算，也就是在i轮循环中，f[j-v]是上一重i循环，f[i-1][j-v]传递下来的
        cin >> v >> w;
        for (int j = V; j >= 0; j--){ //int j = V; j >= v; j--
            if (j >= v){
                f[j]=max(f[j-v]+w,f[j]); 
            } /*else{
                //break; 由于没啥意义可以直接跳过，或者整段删除
                f[j] = f[j];//背包放不下当前巨物就不选. 由于右边这个f[j]在第i层循环时没有计算过，所以是上一层传递下来的f[i-1][j]
            }*/
        }
    }
    cout << f[V] << endl;
    return 0;
}