2,229 views
5.Consider the Knapsack instance with 5 objects and a capacity M=11, profit P=(5,4,7,2,3) and
weight W=(4,3,6,2,2.). Solve it using dynamic programming approach.

### 1 comment

$14$ is the correct answer Using Dynamic Programming $(0/1)$ Knapsack Problem. And $13.5$ Using Greedy Algorithm, Fractional knapsack problem.

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5 5 5 0 0 0 4 5 5 5 9 9 9 9 9 0 0 0 4 5 5 7 9 9 9 9 9 0 0 2 4 5 6 7 9 9 11 12 13 0 0 3 4 5 7 8 9 10 12 12 14

Columns w represents weights <0, 1, 2, 3, ........11>

Rows i represent Item number <0, 1, 2, 3, 4, 5>

cell <i, w> indicates total profit P by "including any/some/all of the first i items in knapsack having combined weight w"

verify it !!

by

1
562 views