# GLPK/Knapsack Problem

From Wikibooks, open books for an open world

< GLPK

The knapsack problem is a classical packing problem from combinatorial optimization.

The knapsack problem can be defined as follows: given a set of items of size and profit , select a subset of those items which fit into capacity and which maximize the collective profit of the chosen items:

maximize | |

subject to |

The knapsack problem belongs to the class of NP-hard problems ^{[1]}.

A usual way to solve knapsack problems is through dynamic programming (DP). The example below shows how to formulate the knapsack problem as a mixed-integer program (MIP) implemented in GMPL (MathProg).

# en.wikipedia.org offers the following definition: # The knapsack problem or rucksack problem is a problem in combinatorial optimization: # Given a set of items, each with a weight and a value, determine the number of each # item to include in a collection so that the total weight is less than a given limit # and the total value is as large as possible. # # This file shows how to model a knapsack problem in GMPL. # Size of knapsack param c; # Items: index, size, profit set I, dimen 3; # Indices set J := setof{(i,s,p) in I} i; # Assignment var a{J}, binary; maximize obj : sum{(i,s,p) in I} p*a[i]; s.t. size : sum{(i,s,p) in I} s*a[i] <= c; solve; printf "The knapsack contains:\n"; printf {(i,s,p) in I: a[i] == 1} " %i", i; printf "\n"; data; # Size of the knapsack param c := 100; # Items: index, size, profit set I := 1 10 10 2 10 10 3 15 15 4 20 20 5 20 20 6 24 24 7 24 24 8 50 50; end;

Now save and run this model using GLPSOL (1 second on an Intel Core i5 processor).

$ glpsol --math knapsack.mod

To yield:

The knapsack contains: 1 4 5 8

## References[edit]

- ↑ Kellerer, Hans; Pferschy, Ulrich; Pferschy, David (2004).
*Knapsack Problems*. Springer-Verlag. ISBN 3-540-40286-1.