Article 4: Greedy Algorithm Explaining using Knapsack Problem
Greedy approach works with some optimization measure that if an input is selected then what would be its effect on total profit measure. For given a set of n inputs, greedy method finds a subset, called feasible solution, of the n inputs subject to some constraints, and satisfying a given objective function. If the objective function is maximized or minimized, the feasible solution is optimal. It is a locally optimal method. Many problems can be solved by greedy approach. One of them is Knapsack problem. The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixedsize knapsack (bag) and must fill it with the most valuable items. As said there are n items in a store. For i =1...