Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Example-0/1 Knapsack Problem

  The 0/1 knapsack problem  is closely related to the change counting problem discussed in the preceding section: We are given a set of n items from which we are to select some number of items to be carried in a knapsack. Each item has both a weight and a profit. The objective is to chose the set of items that fits in the knapsack and maximizes the profit.

Let tex2html_wrap_inline67468 be the weight of the tex2html_wrap_inline57621 item, tex2html_wrap_inline57649 be the profit accrued when the tex2html_wrap_inline57621 item is carried in the knapsack, and C be the capacity of the knapsack. Let tex2html_wrap_inline67478 be a variable the value of which is either zero or one. The variable tex2html_wrap_inline67478 has the value one when the tex2html_wrap_inline57621 item is carried in the knapsack.

Given tex2html_wrap_inline67484 and tex2html_wrap_inline67486, our objective is to maximize

displaymath67462

subject to the constraint

displaymath67463

Clearly, we can solve this problem by exhaustively enumerating the feasible solutions and selecting the one with the highest profit. However, since there are tex2html_wrap_inline60061 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:

Greedy by Profit
At each step select from the remaining items the one with the highest profit (provided the capacity of the knapsack is not exceeded). This approach tries to maximize the profit by choosing the most profitable items first.
Greedy by Weight
At each step select from the remaining items the one with the least weight (provided the capacity of the knapsack is not exceeded). This approach tries to maximize the profit by putting as many items into the knapsack as possible.
Greedy by Profit Density
At each step select from the remaining items the one with the largest profit density, tex2html_wrap_inline67492 (provided the capacity of the knapsack is not exceeded). This approach tries to maximize the profit by choosing items with the largest profit per unit of weight.

While all three approaches generate feasible solutions, we cannot guarantee that any of them will always generate the optimal solution. In fact, it is even possible that none of them does! Table gif gives an example where this is the case.

 

 

greedy by

i

tex2html_wrap_inline67468 tex2html_wrap_inline57649 tex2html_wrap_inline67492 profit weight density optimal solution
1 100 40 0.4 1 0 0 0
2 50 35 0.7 0 0 1 1
3 45 18 0.4 0 1 0 1
4 20 4 0.2 0 1 1 0
5 10 10 1.0 0 1 1 0
6 5 2 0.4 0 1 1 1
total weight 100 80 85 100
total profit 40 34 51 55
Table: 0/1 knapsack problem example (C=100).

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.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.