John Graham-Cunning's Minimum Coin Problems

In The Minimum Coin Problem, John Graham-Cunning poses the following problems:

1. Given a pile of coins and a target amount, find a way to pay exactly that amount using the maximum number of coins from the pile.
2. Given a pile of coins and a target amount, find a way to pay at least that amount using the maximum number of coins from the pile, such that removing any coin from the payment yields an amount that is less than the target amount.
3. Given a pile of coins — each type of coin having a given weight — and a target amount, find a way to pay at least that amount using the maximum weight of coins from the pile, such that removing any coin from the payment yields an amount that is less than the target amount.

These can each be posed as integer programming problems and solved with a solver such as GLPK. Here is a solution to problem 1, a solution to problem 2, and a solution to problem 3.