title: Maximum Coin Partition
body: <p>Since standing at the point of sale in the supermarket yesterday, once more trying to heuristically find an optimal partition of my coins while trying to ignore the impatient and nervous queue behind me, I've been pondering about the underlying algorithmic problem:</p>
  
  <p>Given a coin system with values v<sub>1</sub>,...,v<sub>n</sub>, a limited stock of coins a<sub>1</sub>,...,a<sub>n</sub> and the sum s which we need to pay.
  We're looking for an algorithm to calculate a partition x<sub>1</sub>,...,x<sub>n</sub> (with 0&lt;=x<sub>i</sub>&lt;=a<sub>i</sub>) with x<sub>1</sub>*v<sub>1</sub>+x<sub>2</sub>*v<sub>2</sub>+...+x<sub>n</sub>*v<sub>n</sub> >= s such that the sum x<sub>1</sub>+...+x<sub>n</sub> - R(r) is maximized, where r is the change, i.e. r = x<sub>1</sub>*v<sub>1</sub>+x<sub>2</sub>*v<sub>2</sub>+...+x<sub>n</sub>*v<sub>n</sub> - s and R(r) is the number of coins returned from the cashier. We assume that the cashier has an unlimited amount of all coins and always gives back the minimal number of coins (by for example using the greedy-algorithm explained in SCHOENING et al.). We also need to make sure that there's no money changing, so that the best solution is NOT to simply give all of the money (because the solution would always be optimal in that case).</p>
  
  <p>Thanks for your creative input!</p>