Knapsack restore solution complexity

In order to solve integer knapsack problem, we used iterative memorization algorithm (via n*w sized matrix where n is the number of items, and w is the knapsack's max weight capacity). We were asked to restore the solution (the items inserted to the knapsack) using the matrix. We're not sure about the restore algorithm run time complexity. The restore pseudo code is as follows (where w(j) is the weight of item j and v(j) is the value of item 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

链接地址: http://www.djcxy.com/p/59944.html

上一篇: 背负数量限制

下一篇: 背包恢复解决方案的复杂性