Question

Suppose that the denomination of the coins in a country are c1 > c2 > . . . cn (e.g. 25, 10, 5, 1 for the United States). The problem to consider is: Given an integer a, find the minimum number of coins needed to make a-cents change. (We assume c1 = 1 and we have unlimited supply of each of the coin types, so that it is always possible to make change for any amount a.) For example, let c3 = 4, c2 = 2, c1 = 1 and a = 6. Then there are 6 distinct ways to make 6-cents change: (6 = 6 × 1, 6 = 4 × 1 + 2, 6 = 1 + 1 + 2 + 2, 6 = 2 + 2 + 2, 6 = 1 + 1 + 4, 6 = 2 + 4). So the answer for this problem instance is 2 coins. (a) A simple heuristic strategy for solving this problem is the following: Always pick the coins with the largest value. For example, for US coins, c1 = 1, c2 = 5, c3 = 10, c4 = 25 and a = 63. We will pick: two 25 coins, one 10 coin, three 1 coin. So we use a total of 6 coins. This strategy does not always work. Describe a counter example. Note: this strategy works for US coins (although the proof is not trivial). So your counter example must use a different coin denominations. (b) Describe a dynamic programming formulation for finding the minimum number of coins needed to make the change, as follows: Define an array A[0..n; 0..a]. The entry A[i, j] is the minimum number of coins needed to make j-cents change, using only the coins with the values c1, c2, . . . , ci . Derive a recursive formula for the entry A[i, j]. The entry A[n, a] will be the answer to the problem. (c) Describe a dynamic programming algorithm for calculating A[∗, ∗] in proper order. The runtime of the algorithm should be at most O(na). (d) Describe an algorithm, that uses A[∗, ∗] and any additional information, to output the optimal solution of the problem. (Namely, output the actual coins needed to make the a cents change).

Answer 1

public class coin {

   static long getNumberOfWays(long N, long[] Coins) {
       // Create the ways array to 1 plus the amount to stop overflow
       long[] ways = new long[(int) N + 1];

       // Set the first way to 1 because its 0 and there is 1 way to make 0
       // with 0 coins
       ways[0] = 1;

       // Go through all of the coins
       for (int i = 0; i < Coins.length; i++) {

           // Make a comparison to each index value of ways with the coin
           // value.
           for (int j = 0; j < ways.length; j++) {
               if (Coins[i] <= j) {

                   // Update the ways array
                   ways[j] += ways[(int) (j - Coins[i])];
               }
           }
       }

       // return the value at the Nth position of the ways array.
       return ways[(int) N];
   }

   static void printArray(long[] coins) {
       for (long i : coins)
           System.out.println(i);
   }

   public static void main(String args[]) {
       long Coins[] = { 1, 5, 10, 25 };

       System.out.println("The Coins are:");
       printArray(Coins);

       System.out.println("Distinct Ways:");
       System.out.println(getNumberOfWays(63, Coins));
   }
}