背包问题

01背包

二维数组可以优化成一维数组，V倒序

因为f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}变成

for i=1..N
    for v=V..0
        f[v]=max{f[v],f[v-c[i]]+w[i]};

这里大V由小的V得出，不先算出来大的，先算小的话，将来算大的用到的小的，是被更新过的f[i]不是f[i-1]

01背包初始化

要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。