Given a set of items, each with a weight and a value, determine which items to include in a collection (knapsack) so that the total weight is less than or equal to a given limit and the total value is as large as possible. (Wikipedia)
Pseudo code for a solution can be found on the Wikipedia website.
Note: There are two variations on the knapsack problem. In the 0-1 Knapsack Problem, you must either take an entire item or not. You cannot take half of an item. In the Fractional Knapsack Problem you can take part of an item.
The most common problem is the 0-1 knapsack problem which restricts the number of copies of each kind of item (in the knapsack) to zero or one.
In other words, each item in the list is a single (unique) item. An item is either in or out of the knapsack. (Part of an item can not be in the knapsack; Only the whole thing.)
Find the 0-1 knapsack problem solution using the following data given a maximum weight of 67 lbs.
Calculate and display the optimal solution
| Problem from Wikipedia page | ||
|---|---|---|
| Item | Weight (lbs) | Value |
| 1 | 23 | 505 |
| 2 | 26 | 352 |
| 3 | 20 | 458 |
| 4 | 18 | 220 |
| 5 | 32 | 354 |
| 6 | 27 | 414 |
| 7 | 29 | 498 |
| 8 | 26 | 545 |
| 9 | 30 | 473 |
| 10 | 27 | 543 |
Create an interactive program that allows the user to create their own 0-1 knapsack problem.
Include a name or number for each item? (This may make it easier to read and understand the list when displayed.)
Use a simple menu to start. Can you convert the program to a GUI?