Knapsack Problem

  • Wahl aus einer Menge an Dingen mit Kosten/Aufwand
  • dabei Gewinn maximieren
  • und unter Budget bleiben
max⁡∑j=1ncjxj∑j=1najxj≤bxj∈{0,1}1≤j≤n.\begin{aligned} &\max \sum_{j=1}^{n} c_{j} x_{j}\\ &\sum_{j=1}^{n} a_{j} x_{j} \leq b\\ &x_{j} \in\{0,1\} \quad 1 \leq j \leq n . \end{aligned}