Knapsack Problem

• Wahl aus einer Menge an Dingen mit Kosten/Aufwand
• dabei Gewinn maximieren
• und unter Budget bleiben

$$\begin{array}{rl}& \max \sum _{j=1}^n{c}_j{x}_j\\ & \sum _{j=1}^n{a}_j{x}_j\le b\\ & x_j\in \{0,1\}1\le j\le n.\end{array}$$