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

2025-05-23 13:46:35
推荐回答(1个)
回答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]};