0-1背包

有n种物品，————每种物品只有一个————，第i种物品的体积为Vi， 重量为Wi， 选一些物品放入容量为C的背包中，使得总物品在不超过C的情况下重量尽量大。

若如前面一般，仅凭借剩余体积这个状态，已经无法满足本题要求，因为物品具有唯一性，不能在任意时候都允许使用，为了消除混乱，需要让决策有序化。

引入“阶段”，用d(i,j)表示当前在第i层，剩余容量为j。
d(i,j) = max(d(i+1,j), d(i+1, j-V[i])+w[i])
或者 d(i,j) = max(d(i-1,j), d(i-1, j-V[i])+w[i])
通俗地说，d(i,j)表示“把第i，i+1,i+2,...,n个物品装到容量为j的背包的最大总重量”。

下面是代码，答案在d[i][C]中

for(int i = n; i >= 1; i--){
    for(int j = 0; j <= C; j++){
        d[i][j] = (i == n? 0 : d[i][j]);
        if(j >= V[i]) d[i][j] = max(d[i][j], d[i+1][j-V[i]] + W[i]);
    }
}

j可以反序（因为同一组j不关联，即非此即彼的关系），i也可以反序（但是细节上有一些不同）
另外，当i从1正向时，可以即输即用

for(int i = 1; i <= n; i++){
        scanf("%d %d", &V, &W);
    for(int j = 0; j <= C; j++){
        d[i][j] = (i == n? 0 : d[i][j]);
        if(j >= V) d[i][j] = max(d[i][j], d[i+1][j-V] + W);
    }
}

更奇妙的是，还可以把数组f变成一维滚动数组

memset(int i = 1; i <=n; i++){
        scanf("%d %d", &V, &W);
        for(int j = C; j >= 1; j++){
                if(j >= V) f[j] = max(f[i], f[j-V]+W);
        }
}

为什么可以这样呢？
1 dp的方向从上到下（为了优化读入）
2 dp的方向从右到左，即先将最右进行覆盖，而后面的操作只会用到比j更小的j-V

但是，也正由于如上原因，使得输出路径只能逆序，找到的也不是字典序最小的方案。