Knapsack problem
Knapsack Problem
The knapsack problem is a classic integer programming model: choose items with values and weights without exceeding a capacity.
Problem Statement
Given $n$ items, each item $j$ has:
- value $v_j$
- weight $w_j$
The knapsack has capacity $W$.
Choose the items with maximum total value without exceeding total weight.
Decision Variables
Define a binary variable:
\[y_j=\begin{cases} 1, & \text{if item }j\text{ is chosen},\\ 0, & \text{otherwise}. \end{cases}\]Model
The $0$-$1$ knapsack problem is:
\[\max \sum_{j=1}^n v_jy_j\]subject to:
\[\sum_{j=1}^n w_jy_j\le W\] \[y_j\in\{0,1\}, \qquad j=1, \ldots,n.\]Interpretation
The objective adds the value of selected items.
The capacity constraint adds the weight of selected items and prevents it from exceeding $W$.
LP Relaxation
The LP relaxation replaces:
\[y_j\in\{0,1\}\]with:
\[0\le y_j\le 1.\]This allows fractional items, which may not be meaningful for the original problem.
Applications
Knapsack-type models appear in:
- budget allocation
- project selection
- cargo loading
- portfolio selection
- resource allocation
- machine scheduling
See Also
Exam checkpoint
For ILP questions, state clearly which variables are integer or binary. Do not use the LP relaxation answer as the integer answer unless it is already integral.