|
The knapsack problem
|
|
A wanderer wants to pack various articles into his knapsack. Each article has a certain utility for him (e.g., a value measurable in €), as well as a certain weight and a given volume. Unfortunately, the knapsack has a limited capacity with respect to weight and volume. Which articles shall be packed into the knapsack such that its content has maximum utility under the capacity constraints?
For instance, let the articles A, B, C and the capacity limits be given by the following table.
| article |
|
|
|
||||||
| A | 6 | 3 | 10 | ||||||
| B | 3 | 2 | 8 | ||||||
| C | 1 | 1 | 2 | ||||||
| capacity | 8 | 5 | - |
Article A thus has a volume of 6 m3, a weight of 3 kg, and a value of 10 €. The knapsack carries at most 8 m3 und 5 kg.
With Dynamic Programming, a method of Operations Research, the problem is solved as multistage desision problem. However, for this small example you may find the solution by simple enumeration:
1 - 0 - 1 (read: take A, C),
with a value of 12 €. Please press the start button to let solve an arbitrary knapsack problem (You can determine the number of articles, but at present the number of columns cannot be changed):
If you only see a gray area instead of a clickable button directly above this line, the probable reason is that you have not installed the newest Java plug-In. The applet is based upon the Java 2 classes (Swing), so to use it your browser needs the Java plug-in version 1.3 or higher. You can download it for free from the SUN website:
http://java.sun.com/getjava/download.html
or
http://java.sun.com/products/plugin/
| © de Vries 2002 |
|
|