Knapsack Problem in DAA | Greedy Approach

What is Knapsack Problem in DAA? | its Algorithm | its Complexity

What is Knapsack Problem in DAA?

---->Knapsack Problem in DAA is the problem solved with Greedy Approach.

Algorithm

----> for i = 1 to n

calculate Profit / Weight

Sort the object in decreasing order of P/W ratio

for i = 1 to n

if M > 0 & wi <= M

M = M - wi

P = P + Pi

else break

if(M > 0)

P = P + Pi (M/wi)

Complexity

----> n (log n)

Example:-
Where M is 20.

Solution:- 1) By Considering the maximum profit.

2) By Considering the objects with minimum profit.

3) By Considering the object with Pi/wi ratio decreasing order.

Questions: Find the optimal solution for Knapsack Problem where n = 7 and M = 15 where,

(P1, P2, P3, P4, P5, P6, P7) = (10, 5, 15, 7, 6, 18, 3)

(W1, W2, W3, W4, W5, W6, W7) = (2, 3, 5, 7, 1, 4, 1)

......................................Solutions will be uploaded soon...................................