Massive Algorithms: Dynamic Programming: Minimum # coins required to make change

Dynamic Programming: Minimum # coins required to make change
http://comproguide.blogspot.com/2013/12/minimum-coin-change-problem.html

http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

There are C different denominations of coins/bills in use with values: v 1 < v 2 < ... < v C (So that we can always make change for any amount) You need to pay someone a certain amount of money $N Find the minimum # of coins/bills that you need to use to make the change for $N

First Define sub problems and how to solve original problem with solutions of sub-problems.
Another Solution: http://www.algorithmist.com/index.php/Min-Coin_Change
http://www.fgdsb.com/2015/01/03/coin-change-problem/


nt minCoins(int a[], int n, int t){

    vector<int> dp(t+1,0);

    int minVal;

    for(int i = 1; i <= t; i++){

        minVal = i;

        for (int j = 0; j < n; j++)

            if(a[j] <= i)

                minVal = min(dp[i-a[j]]+1,minVal);

            else

                break;

        dp[i] = minVal;

    }

    return dp[t];

}

C (N, m) = min(C (N, m - 1), C (N - S m, m) + 1)

with the base cases:

$C (N, m) = 1, N = 0$
$C (N, m) = 0, N < 0$
$C( N, m ) = 0, N \geq 1, m \leq 0$

Define:

M(j) = the minimum # coins/bills to make change for j (money units)

How can we:

Divide the problem M(j) into smaller subproblems
And then use the solution(s) of the smaller problem(s) to solve the original problem M(j

Bottom-up Dynamic programming version

static int findM(int Am, int v[])
    {
       int[] M;
       int[] sol, mySol;
       int j, k, min;

       M = new int[Am+1];              // Store results

       sol = new int[v.length];
       mySol = new int[v.length];

       /* ---------------------------
          Base case
          --------------------------- */
       M[0] = 0;        // 0 coins needed to make change for $0

       /* ---------------------------------------------------
          The other cases (starting from 1 to M.length - 1)

   Follow direction of data flow !
          --------------------------------------------------- */
       for ( j = 1; j <= Am; j++ )
       {
          /* ============================================
      Find min # coin to make change for $j
      ============================================ */

          for ( k = 0; k < v.length; k++ )
             mySol[k] = -1;                   // Initialize mySol[]

          /* --------------------------------------------------------
             Try every denomination k = 1,2,..,C for the last coin
             -------------------------------------------------------- */
          for ( k = 0; k < v.length; k++ )
          {
             /* --------------------------------------------
                Check if we can use the k-th denomination
                -------------------------------------------- */
             if ( v[k] <= j )
             {
                /* ------------------------
                   Divide step
                   ------------------------ */
                sol[k] = M[j - v[k]];     // Use coin v[k] as last coin
                mySol[k] = sol[k] + 1;    // Solution to make change for $j      
             }
          }

          /* --------------------------------------------------------
             Find the minimum of all mySol[...]
             -------------------------------------------------------- */
          M[j] = -1;

          for ( k = 0; k < v.length; k++ )
          {
             if ( mySol[k] > 0 )
             {
                if ( M[j] == -1 || mySol[k] < M[j] )
                   M[j] = mySol[k];
             }
          }
       }

       return( M[Am] );    // Min # coins to change $Am
   }

Dive and Conquer

static int M(int j, int[] v)
    {
       int[] sol, mySol;
       int   myFinalSol;
       int k;

       sol = new int[v.length];
       mySol = new int[v.length];

       /* ---------------------------
          Base cases
          --------------------------- */
       if ( j == 0 )
       {
           return(0);
       }
          
       /* ==================================================
          Initialize mySol[]
   ================================================== */
       for ( k = 0; k < v.length; k++ )
          mySol[k] = -1;                   // -1 means: no solution

       /* --------------------------------------------------------
          Try every denomination k = 1,2,..,C for the last coin
          -------------------------------------------------------- */   
       for ( k = 0; k < v.length; k++ )
       {
          /* --------------------------------------------
             Check if we can use the k-th denomination
             -------------------------------------------- */
          if ( v[k] <= j )
          {
             /* ------------------------
                Divide step
                ------------------------ */
             sol[k] = M(j - v[k], v);  // Use coin v[k] as last coin

             mySol[k] = sol[k] + 1;    // Solution to make change for $j   
          }
       }

       /* --------------------------------------------------------
          Find the minimum for ALL mySol[...] values

   Note: -1 means do NOT use !
          -------------------------------------------------------- */
       myFinalSol = -1;

       for ( k = 0; k < v.length; k++ )
       {
          if ( mySol[k] >= 0 /* Don't use -1 values */ )
          {
             if ( myFinalSol == -1 || mySol[k] < myFinalSol )
                myFinalSol = mySol[k];
          }
       }

       return(myFinalSol);   // Return best solution
   }

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

http://n1b-algo.blogspot.com/2009/01/optimal-coin-change-problem.html
https://github.com/n1balgo/algo/blob/master/coin_change.py
def optimal_change(Amt, Currency, Inf):
# array which contains optimal number of coins required for [0,1,...,Amt] amount
num_coins = [0] # we need zero coins to give a change of 0 amount

# array which contains the optimal change to reach that amount
selected_change = [0]

# start with 1 and go till Amt
for i in xrange(1, Amt+1):

# num_coins required for amount = i
nc_i = Inf

# selected change for amount = i
sc_i = Inf

# iter over all coins in the currency
for c in Currency:

# if c is smaller than required amount and num coins to reach i-c is one less
# than num coins (nc), then update local variables
if i >= c and nc_i > num_coins[i-c] + 1:
nc_i = num_coins[i-c] + 1
sc_i = c

# update optimal arrays
num_coins.append(nc_i)
selected_change.append(sc_i)

# num_coins and selected_change can be used to print the coins required to get optimal change
return [num_coins, selected_change]

def trace_optimal_solution(Amt, num_coins, selected_change):
Amt0 = Amt

# coins that are used to make the change for Amt
coins = {}

nc = num_coins[Amt]
while nc > 0:
# get the selected coin
sc = selected_change[Amt]

# add sc to coin map
if coins.has_key(sc):
coins[sc] += 1
else:
coins[sc] = 1

# update Amt
Amt = Amt - sc

# get num coins require to attain Amt
nc = num_coins[Amt]

print "Optimal soln for", Amt0, "uses", num_coins[Amt0], "coins:", coins
return coins

def greedy_change(Amt, Currency):
Amt0 = Amt
num_coins = 0
coins = {}

# we want to get as much change for max currency first, hence reverse sorting is required
Currency = sorted(Currency, reverse=True)

for c in Currency:
# we can pay with c
if c <= Amt:

# number of c coins to pay
n = int(Amt/c)

# decrement amount
Amt = Amt - n * c

# update vars
num_coins += n
coins[c] = n

print "Greedy soln for", Amt0, "uses", num_coins, "coins:", coins
return num_coins

Read full article from Dynamic Programming: Minimum # coins required to make change

Dynamic Programming: Minimum # coins required to make change

Labels

Popular Posts