Das klassische Knapsack-Problem ist ein kombinatorisches Optimierungsproblem und kann nicht direkt durch ein lineares Optimierungsmodell gelöst werden, da es sich um ein Problem mit ganzzahligen Variablen handelt. Es kann jedoch durch ein ganzzahliges lineares Programm (Integer Linear Programming, ILP) formuliert und gelöst werden. Die Formulierung des Knapsack-Problems als ILP sieht wie folgt aus: Maximiere: \[ \sum_{i=1}^{n} v_i x_i \] unter den Nebenbedingungen: \[ \sum_{i=1}^{n} w_i x_i \leq W \] \[ x_i \in \{0, 1\} \quad \text{für alle } i \] Hierbei ist: - \( v_i \) der Wert des \( i \)-ten Gegenstands, - \( w_i \) das Gewicht des \( i \)-ten Gegenstands, - \( W \) die maximale Kapazität des Rucksacks, - \( x_i \) eine binäre Variable, die 1 ist, wenn der \( i \)-te Gegenstand in den Rucksack aufgenommen wird, und 0, wenn nicht. Diese Formulierung kann mit speziellen Algorithmen für ganzzahlige lineare Programme gelöst werden, wie z.B. dem Branch-and-Bound-Algorithmus oder dem Branch-and-Cut-Algorithmus.