The KNAPSACK.lng Model

Knapsack Model

View the model

Download the model

The *knapsack* model is a classic problem in which binary variables are put to use. In this type of problem, you have a group of items you want to pack into your knapsack. Unfortunately, the capacity of the knapsack is limited such that it is impossible to include all items. Each item has a certain value, or utility, associated with including it in the knapsack. The problem is to find the subset of items to include in the knapsack that maximized the total value of the load without exceeding the capacity of the knapsack. This model can be generalized to many other areas such as truck loading, bin packing, choosing science experiments for the Space Shuttle, and so on.

In this example, you are planning a picnic. You've constructed a list of items you would like to carry with you on the picnic. Each item has a weight associated with it and your knapsack is limited to carrying no more than 15 pounds. You have also come up with a 1 to 10 rating for each item, which indicates how strongly you want to include the particular item in the knapsack for the picnic. You need to select items to be placed into your knapsack to maximize a measure of utility without exceeding the capacity of the knapsack.

Keywords:

Shipping | Knapsack Model | Transportation |