How can this class of problem be solved in general?
Six friends get together to play poker. To start, each player buys fifty \$1 chips from the banker with a \$50 bill.
At the end of the game, the banker buys back each player's chips using a combination of \$1, \$5, \$10, \$20 bills and the six \$50 bills. What quantity of each bill should the banker have on hand in order to buy back all \$300 of chips, while minimizing the number of bills on hand?
Empirically, up to 5 players might need 4 \$1 bills. All 6 players might need 1 \$5 bill. (If a player needed two \$5 bills, it would be better to pay him with one \$10 bill.) All 6 players might need 1 \$10 bill (If a player needed two \$10 bills, it would be better to pay him with one \$20 bill.) Up to 5 players might need 2 \$20 bills. This adds up to \$310 in bills that the banker must have in hand, comprising 42 bills (not counting the \$50 bills). Is this the minimum number of bills?
Is this analysis correct? Is there a way to solve the generalized problem?
You can solve the problem via integer linear programming as follows.
As you observed, at least $20$ \$1 bills are necessary. As a simplifying assumption, set those $20$ bills aside to pay off the player amounts $\mod 5$. From now on, consider player amounts that are multiples of $5$ and add up to $300-20=280$. Let $P$ be the set of players, and let $x_p$ be the amount owed to player $p\in P$. Any amounts that are at least $50$ can be partially paid with the given \$50 bills. Without loss of generality, $x_1 \le x_2 \le \dots \le x_6 \le 49$. It turns out that there are $504$ such scenarios. Let $S$ be the set of scenarios, and let $\bar{x}_{p,s}$ be the value of $x_p$ in scenario $s\in S$. The banker needs enough bills to pay off the players in each scenario. Let $D=\{5,10,20\}$ be the denominations of the bills other than \$1 and \$50. Let nonnegative integer decision variable $y_{d,p,s}$ be the number of \$$d$ bills needed to pay player $p$ in scenario $s$. Let nonnegative integer decision variable $z_d$ be the number of \$$d$ bills needed by the banker. The problem is to minimize $$20+\sum_{d\in D} z_d$$ subject to \begin{align} \sum_{d\in D} d \cdot y_{d,p,s} &= \bar{x}_{p,s} &&\text{for $p\in P$ and $s\in S$} \tag1\label1 \\ \sum_{p\in P} y_{d,p,s} &\le z_d &&\text{for $d\in D$ and $s\in S$} \tag2\label2 \end{align} Constraint \eqref{1} pays each player the correct amount in each scenario. Constraint \eqref{2} forces the banker to have enough \$d bills in each scenario.
The optimal objective value turns out to be $39$, attained by $z_5=6$, $z_{10}=6$, and $z_{20}=7$. So $39$ bills suffice.
Because we made a simplifying assumption about the \$1 bills and $x_p \equiv 0 \pmod 5$, it is conceivable that an even better solution exists. In principle, the same approach can be applied, with $D=\{1,5,10,20\}$ and without the $\mod 5$ assumption, but the number of scenarios to consider would be much larger ($|S|=579852$ instead of $|S|=504$).
It turns out that $39$ is in fact optimal. For a short proof of the lower bound, consider the following scenario: $$x_1=35, x_2=x_3=x_4=39, x_5=49, x_6=99$$ Clearly, at least $5\cdot4=20$ \$1 bills are needed, leaving $$x_1=x_2=x_3=x_4=35, x_5=45, x_6=95$$ Using any more \$1 bills would be wasteful, so at least $6$ \$5 bills are needed, leaving $$x_1=x_2=x_3=x_4=30, x_5=40, x_6=90$$ Using any more \$5 bills would be wasteful, so at least $4$ \$10 bills are needed, leaving $$x_1=x_2=x_3=x_4=20, x_5=40, x_6=90$$ Using any more \$10 bills would be wasteful, so at least $8$ \$20 bills are needed, leaving $$x_1=x_2=x_3=x_4=x_5=0, x_6=50$$ Now at least $1$ bill is still needed, and a \$50 bill suffices. So even if there were no other scenarios, the banker would need at least $20+6+4+8+1=39$ bills.
You claimed:
It might be a useful exercise to verify that the scenario you had in mind can be satisfied with only $7$ \$20 bills instead, by also using the $6$ \$5 bills and $6$ \$10 bills. The intuition for why $42$ bills can be improved is that in order to minimize the overall number of bills needed, some scenarios might not use the fewest number of bills possible.