<p>If all the conversions are integers, and there is a least common measure which can be identified with 1 unit of value (it looks like your coin E would be such a thing), then the problem reduces to the classic change-making problem. </p>

<p>In North America we have 1 cent, 5 cent, 10 cent, 25 cent (ignoring higher valued coins). With that system, a greedy algorithm works: take the largest coin you can at each step. The result of that process is the minimum number of coins to make change. We say the system {1, 5, 10, 25} is <strong>canonical</strong> because the greedy algorithm works.</p>

<p>For other systems of coins, the greedy algorithm does not work. For example, if there are no 5 cent pieces, the greedy algorithm applied to 30 cents yields 25 + 1 + 1 + 1 + 1 + 1, six coins, whereas the minimum is 10 + 10 + 10, three coins. We say the system {1, 10, 25} is not canonical.</p>

<p>The simplest way to approach your problem is to set up a canonical system of coins, then just use the greedy algorithm. A simple canonical system is {1, 5, 10, 25} mentioned above. If you want something funkier you can use arithmetic progressions, geometric progressions, or Fibonacci numbers. Other examples and a general discussion can be found at <a href="http://arxiv.org/pdf/0809.0400.pdf" rel="nofollow">http://arxiv.org/pdf/0809.0400.pdf</a>.</p>

<p>If you want to use a non-canonical system, or if you want to use a system and can't prove that it's canonical, there's a dynamic programming solution. Let <code>n[i]</code> be an array from <code>0</code> to <code>v</code>, the amount for which you want to make change (e.g., in the example I gave above, <code>v = 30</code>). <code>n[i]</code> represents the minimum number of coins needed to make change for value <code>i</code>. We know <code>n[0] = 0</code>, and <code>n[1] = 1</code> (because there is a 1 cent piece). Then we calculate the other <code>n[i]</code> in order. <code>n[i] = min { n[i-c]+1 where c is a coin in the set}</code>. So in the example {1, 10, 25}, we have <code>n[2] = min {n[2-1]+1} = 2</code>, <code>n[3] = min {n[3-1]+1} = 3</code>, <code>n[4] = min{n[4-1]+1} = 4</code>, ..., <code>n[9] = 9</code>, and <code>n[10] = min {n[10-1]+1, n[10-10]+1} = min {10,1} = 1</code>, ... . Once you have <code>n[v]</code>, you work backwards, figuring out which coin <code>c</code> results in <code>n[v-c] &lt; n[v]</code>, and continue in that manner until you hit zero.</p>

<p>The dynamic programming solution is slower than the greedy algorithm ... much slower for large values <code>v</code> ... and it's more complicated to program and more error-prone. So I suggest you first check whether your system is canconical. If it isn't, you can change the system. If you are stuck with a non-canonical system in circulation, you can introduce new coin values to it to make it canonical. Then you can use the greedy algorithm.</p>
Minimizing Number of Coins After Buying An Item
<p>I came up with this algorithmic problem while trying to solve a problem in my (adventure-based) program.
There are 5 different types of coins called, A,B,C,D,E (from most valuable to least valuable). The conversions between
the coin values are AtoE, BtoE, CtoE, DtoE (i.e. AtoE means that a coin of type A is worth AtoE times the value of a
coin of type E).  The struct <code>Currency</code> represents how much money a customer has.  The goal of the function</p>

<pre><code>template &lt;int AtoE, int BtoE, int CtoE, int DtoE&gt;
void purchase (int numCoins, CoinType coinType, int a, int b, int c, int d, int e)
</code></pre>

<p>is to have the customer (who has <code>a</code> coins of type <code>A</code>, <code>b</code> coins of type <code>B</code>, etc...) to purchase an item whose
price is <code>numCoins</code> <code>coinType</code>s while minimizing the amount of coins he has after receiving the change.
Can someone suggest the pseudocode for the body of this function to get the correct resulting change to
minimize the resulting number of coins?  Optimization would be nice to, but first how to get it working?
I'm really stuck here.  Here I've written the starting code in C++, but the problem is language-independent.</p>

<pre><code>#include &lt;iostream&gt;
#include &lt;array&gt;
#include &lt;algorithm&gt;

enum CoinType {A, B, C, D, E, NumCoinTypes};

struct Currency {
    std::array&lt;int, NumCoinTypes&gt; coins;
    Currency (int a, int b, int c, int d, int e) : coins ({a,b,c,d,e}) {}
    void print() const {
        for (int x : coins) std::cout &lt;&lt; x &lt;&lt; ' ';
        std::cout &lt;&lt; "  total coins = " &lt;&lt; std::accumulate (coins.begin(), coins.end(), 0) &lt;&lt; '\n';
    }
};

struct Item {
    struct Value { int numCoins;  CoinType coinType; };
    Value value;
};

template &lt;int AtoE, int BtoE, int CtoE, int DtoE&gt;
void purchase (int numCoins, CoinType coinType, int a, int b, int c, int d, int e) {
    const Item item {numCoins, coinType};
    Currency currency(a,b,c,d,e);
    std::cout &lt;&lt; "Before paying for the item: ";  currency.print();
    // Goal:  Purchase 'item' so that the change in 'currency' due to paying for 'item'
    // and receiving the change minimizes the number of coins in 'currency'.
    // Modify 'currency' somehow here.


    std::cout &lt;&lt; "After paying for the item: ";  currency.print();
}

int main() {
    purchase&lt;5,10,8,15&gt;(50, C, 1,2,5,40,30);  // Sample test run.
}
</code></pre>

<p>There have been some references to the Knapsack Problem, but I'm not sure it applies here.  The amount of money S that is given to the cashier is not known. Thus the change received, which is <code>S - price</code>, is not fixed, so it does not appear to me that the knapsack problem applies.  Perhaps, once could try all possible (reasonable) values of S and then apply a Knapsack algorithm to each S value.  But the amount of change comprising the currency not given to the cashier also depends on what S was (and the currency used to hand over the amount S).  The amount of coins being minimized is not just that which adds up to <code>S - price</code>, but rather ALL the coins, including those not given to the cashier (which, again, depends on S and the currency to make up S).  Also, the number of coins for each coin type in the result is not just 1 or 0.</p>

<p><strong>Update:</strong>  Thanks to Edward Doolittle's algorithm, the problem has been solved (my implemented code in one the answers below), but the solution makes one assumption:  that the customer pays for the item with ALL the coins he possesses.  Mathematically, the optimized change does give the correct answer, but it doesn't simulate the real world too well.  Would a customer carrying a huge bag of change really pour out ALL his change to buy a candy???</p>

<p>So now I stipulate a condition that will seek a second solution.  This second solution will not minimize the resulting number of coins like the first solution, but it does give a more realistic result.  This new condition is:</p>

<p><strong>The customer shall pay for the item with some of his coins such that he pays enough to purchase the item without paying any redundant coins.</strong></p>

<p>For example, if 4 quarters is enough to purchase the item, he shall NOT pay a 5th quarter (nor shall he add any pennies or whatever on top of these 4 quarters).  This condition is pretty much what the typical customer in the real world follows when purchasing an item.  So here is the algorithm I've thought of for determining what coins the customer shall pay to minimize his number of coins at the end while following the above condition:  The total payment will be with as many of the cheapest coins as possible, then (if these are not enough), with as many of the second cheapest coin as possible, then (if these are also not enough), with as many of the third cheapest coin as possible, and so forth.  However, I'm not sure if this is the correct algorithm, and even if it is, it needs mathematical proof.  I've written a solution using this algorithm and provided it as another answer.</p>