Answer to Question #323571 in Algorithms for manisha

Question

Find an optimal solution for the knapsack instance n=6 and M=13,

(p1 , p2 ,..., p6 )=(8, 5, 13, 7, 6, 15)

(w1 , w2 ,..., w6 )=(3, 2, 4, 6, 2, 5)

Answer 1

Solve the problem using dynamic programming:

m[i, w] is the maximal price of a knapsack with a weight no more than w which include first i items

Then we have recursion

m [ 0 , w ] = 0

m [ i , w ] = m [ i − 1 , w ] if w_i > w

m [ i , w ] = max (m [i−1, w ], m[i−1 , w−w_i] + p_i) if w_i <= w

              w  =  1   2   3   4   5   6   7   8   9  10  11  12  13
i wi  pi m[0, w] = (0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0)
1  3   8 m[1, w] = (0,  0,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8)
2  2   5 m[2, w] = (0,  5,  8,  8, 13, 13, 13, 13, 13, 13, 13, 13, 13)
3  4  13 m[3, w] = (0,  5,  8, 13, 13, 18, 21, 21, 26, 26, 26, 26, 26)
4  6   7 m[4, w] = (0,  5,  8, 13, 13, 18, 21, 21, 26, 26, 26, 26, 28)
5  2   6 m[5, w] = (0,  6,  8, 13, 14, 19, 21, 24, 27, 27, 32, 32, 32)
6  5  15 m[6, w] = (0,  6,  8, 13, 15, 19, 21, 24, 28, 29, 34, 36, 39)

m[6,13] gives optimal solution 39