0/1背包就是一个简单的动态规划问题。最简单的递推式是二维递推,但是人们在实践中发现二维递推有很多空间只被用了一次,所以抽象出了一维数组保存的递推,本质上还是二维,但空间复杂度降低到了O(V),时间复杂度仍然是0(N*V)的。
伪代码如下:
for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]};