Question

算法设计与分析 0/1背包问题

算法设计与分析 0/1背包问题求大神帮忙写一下程序 蛮急的

要求要用到蛮力算法，递归算法，动态规划算法以及对各个算法时间复杂度进行比较分析，还需要相应的菜单

Answer 1

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