Change-Making Problems
Why
Suppose a cashier needs to provide $c \in \Z _+$ cents in change, and wants to do so using the using the fewest (or most) number of coins, each worth a different number of cents. We can model this as a problem similar to the bounded knapsack problem, in which we have an equality constraint instead of an inequality one.
Definition
Given $w: \set{1, \dots , n} \to \R _+$, $b
\in \Z _+^n$, find $x \in \Z _+^n$ to
\[
\begin{aligned}
\text{minimize} & \quad \sum_i x_i \\
\text{subject to} & \quad \sum_{j = 1}^n w_j x_j = c \\
& \quad 0 \leq x \leq b, x \in \Z _{n}^{+}
\end{aligned}
\]