Question

ALGORITHM

Given the following Knapsack problem instance and its DP solution: 1 2 3 4 5 weight value To 10 10 10 10 item1 1 10 item2 | 2 17 item3 11 11 21 21 28 28 item4 15 0 11 121 121 128 36 According to the solution table, the maximum item value that we can achieve 36. By reconstructing the solution, we know that the following items {1,3,4} are included in the solution. Carefully, fill in the following blanks: • The answer to the problem appears at cell <4,5> in the matrix. • The cell in the table that lets me pick item4 is cell at location: • The cell in the table that lets me pick item3 is cell at location: • The cell in the table that lets me pick item1 is cell at location:

Answer 1

a) Maximum profit is 36 and it is generated only by the 5th row at index (4,5). Therefore, it is this cell that lets me pick item 4.

Remaining profit is 36-value of item4 = 36-15 = 21.

b) Maximum profit now has become 21 and it is generated only by the 4th row at index (3,2) at the earliest, therefore, it is this cell that lets me pick item 3.

Remaining profit would be 21-value of item3 = 21-11 = 10.

c) Maximum profit now has become 10 and is generated by both third and second row, but in the first row the earliest at index (1,1) and no row above this row contains 10, therefore, it is this cell that lets me pick item 1.

Remaining profit = 10-10 = 0.

Hope the above solution solves your doubt. Thank you:)