ABSTRACT
The knapsack problem appears as a fundamental subproblem in seemingly countless optimization problems, and is a deceptively simple looking problem that can be used to illustrate the attention to detail required in analyzing optimization models. The problem can be easily explained as follows. Suppose you have a knapsack with a capacity that can be measured using a single dimension (e.g., weight). You have a number of individual items that you would like to take with you in the knapsack, but the collective set of items will not t in the knapsack. That is, the collective capacity consumption of the individual items exceeds the knapsack's capacity. Each of these items has a value to you and you would like to maximize the total value of the items that you take with you in the knapsack. The goal is to determine the subset of items to put in the knapsack (without exceeding the knapsack capacity) that maximizes the total value of items you carry with you. Clearly if each item consumes exactly one unit of knapsack capacity, then the problem is trivial. We simply need to sort the items in nonincreasing value order (breaking ties arbitrarily), and insert them into the knapsack in this order until either the knapsack is full, or until we have inserted all items with positive (or nonnegative) value. Similarly, if all items have the same value, then we insert items into the knapsack in nondecreasing order of capacity consumption levels. When the items consume dierent levels of capacity and have dierent values, however, the problem becomes substantially more dicult.
