Question

In your own words describe the ‘knapsack problem’. Further, compare and contrast the use of a brute force and a dynamic programming algorithm to solve this problem in terms of the advantage and disadvantages of each. An analysis of the asymptotic complexity of each is required as part of this assignment.

Answer 1

Knapsack problem is described as :-

Given a set of n items I₁, I₂,....,I_n with weight w₁, w₂,...,w_n and values v₁,v₂,....,v_n and a knapsack of capacity C, our goal is to carry as much item as possible in knapsack within capacity C such that sum of value of items within Knapsack is maximized.

While Brute force approach try to check for all possible set of combination of items and hence there are 2ⁿ possible ways of inserting items and Brute force method check for all possibility.

On the other hand dynamic programming approach build the solution over smaller set of items and then extend the solution over larger set of items. Thus if KNAP(m, C₁) is optimal solution of wet of items from index 1 to m with knapsack capacity C₁ then using this solution for KNAP(m, C₁+1) and KNAP(m+1,C₁) is build and hence finally KNAP(n, C) is the desired solution.

Both dynamic programing and Brute force technique will give optimal solution.

Dynamic programing build the solution in time complexity O(nC) while brute force algorithm will build solution in time O(n2ⁿ).

Advantage of Dynamic programing over brute force is that former is faster when C <2ⁿ.

Disadvantage of dynamic programing is then it will be slower if C > 2ⁿ.

Please comment for any clarification .