Greedy method is best suited to
solve more complex problems such as a knapsack problem.
In a knapsack problem
there is a knapsack or a container of capacity M n items where, each item i is
of weight wi and is associated with a profit pi. The problem of
knapsack is to fill the available items into the knapsack so that the knapsack
gets filled up and yields a maximum profit. If a fraction xi of object i is
placed into the knapsack, then a profit pixi is earned. The constrain is that all chosen objects
should sum up to M
Illustration
Consider a knapsack problem of
finding the optimal solution where, M=15, (p1,p2,p3…p7) = (10, 5, 15, 7, 6, 18,
3) and (w1, w2, …., w7) = (2, 3, 5, 7, 1, 4, 1).
In order to find the solution,
one can follow three different srategies.
Strategy 1 : non-increasing profit values
No comments:
Post a Comment