Let be the weight of the item, be the profit accrued when the item is carried in the knapsack, and C be the capacity of the knapsack. Let be a variable the value of which is either zero or one. The variable has the value one when the item is carried in the knapsack.
Given and , our objective is to maximize
subject to the constraint
Clearly, we can solve this problem by exhaustively enumerating the feasible solutions and selecting the one with the highest profit. However, since there are possible solutions, the running time required for the brute-force solution becomes prohibitive as n gets large.
An alternative is to use a greedy solution strategy which solves the problem by putting items into the knapsack one-by-one. This approach is greedy because once an item has been put into the knapsack, it is never removed.
How do we select the next item to be put into the knapsack? There are several possibilities:
The bottom line about greedy algorithms is this: Before using a greedy algorithm you must make sure that it always gives the correct answer. Fortunately, in many cases this is true.