背包恢复解决方案的复杂性
为了解决整数背包问题，我们使用迭代记忆算法（通过n*w大小的矩阵，其中n是项目的数量，并且w是背包的最大权重容量）。 我们被要求用矩阵恢复解决方案（插入背包的物品）。 我们不确定恢复算法运行时间的复杂性。 恢复伪代码如下（其中w(j)是项目j的权重， v(j)是项目j的值）：
**RestoreItems(M)**
I is an empty set.
j=n, T = W.
while j>0 and T>0
if M[j,T] = M[j-1,T]
j=j-1
if M[j,T] = M[j-1,T-w(j)] +v(j) and w(j) <= T
I = I + j
j = j-1
T = T - w(j)
return I