In the knapsack problem, there is a knapsack (a bag) of limited capacity and a number of items, each with a value and a weight. The objective of the knapsack problem is to fill the bag with items such that it contains the maximum possible value without exceeding its capacity, which is some pre-specified weight limit. Each item either be put in the bag (included), or left out (excluded).
Example: the knapsack has a maximum weight capacity of 20kg.
The items are:
| Item # | Weight (in kg) | Value (in Euro) |
| 1 | 10 | 11 |
| 2 | 5 | 3 |
| 3 | 15 | 13 |
A knapsack that contains item 1 and item 2 has a value of 14€ and weighs less (15kg) than the capacity (20kg). A knapsack which contains item 1 and item 3 has a value of 24€ but cannot be selected, as its weight (25kg) exceeds the capacity (20kg). The best knapsack (or the solution to the problem) is that containing item 2 and item 3, with a value of 16€ and a weight of 20kg.
You are free to verify that this is indeed the best knapsack before moving onto the next page.
In the following rounds you will face knapsack problems which are harder to solve than this one. You will also have a time limit of 240 seconds (4 minutes) to solve each one.
Your payoffs will depend on the value of the knapsack that you submit, in particular: at the end of the experiment, the computer will randomly pick one of the knapsack problems you solved. The maximum payoff will be 10€ and will be scaled according to how far the value of your knapsack was from the value of the best possible knapsack.
For example, suppose that on the round that the computer picked, the best knapsack had a value of 100 and your submission had a value of 76. Then, your payment would be (76/100)*10€ = 7.60€.
Try to submit your best knapsack within the time limit, even if you are not able to find the best knapsack.
Good luck!
{{ next_button }} {{ endblock }}