in Algorithms edited by
2,229 views
0 votes
0 votes
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.
in Algorithms edited by
2.2k views

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

1 Answer

1 vote
1 vote

 

                                

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 !!