Change Making Problem

The change making problem is an optimization problem that asks”What is the minimum number of coins I need to make up a specific total?”The input to the Change Making Problem is a sequence of positive integers[d1, d2, d3 … dn]andT, wheredirepresents a coin denomination andTis the target amount. Assuming an unlimited supply of coins of each denomination, we need to find the number of coinsNrequired to form the given amount. An extra effort would be to find the exact coins to build up the amount.The above problem represents an optimal sub-structure, which means
that the problem can be broken down into smaller parts. Suppose there
is an optimal solution for amountTand if we break the target
amount into two partsmandT-m, then there will be optimal
solution for making amountmusing some portion from the optimal
solution for amountTand the remaining coins from the solution will
be the optimal solution for making amountT-m.Let C[m] be the minimum number of coins of denominations d1,d2,…,dk needed to make change for m amount. In the optimal solution to making change formamount, there must exist some first coindi, wheredi < m. Furthermore, the remaining coins in the solution must themselves be the optimal solution to making change form- di.Thus, ifdiis the first coin in the optimal solution to making change for m amount, thenC[m]=1 + C[m – di]i.e. one di coin plusC[m – di]coins to optimally make change form – diamount. We don’t know which coindiis the first coin; however, we may check all n such possibilities (subject to the constraint thatdi < m), and the value of the optimal solution must correspond to the minimum value of1 + C[m – di], by definition.Furthermore, when making change for 0, the value of the optimal solution is clearly 0 coins. We thus have the following recurrence.C[p] = 0 if p = 0
min(i: di < p) {1 + C[p – di]} if p > 0Below is the code given for the above algorithm#include <iostream>
#define N 4
#define C 17
using namespace std;

// In this example we take the amount as 17, and a total of
// 4 denominations of coins

int main()
{
// contains the coin denominations
int coins[N]={1,2,5,10};

// C[i] contains the minimum number of coins required
// to form the sum i
int amount[C+1]={0};

for(int amt = 1; amt <= C ;amt++)
{
amount[amt] = INT_MAX;
int temp = INT_MAX;
for(int c = 0; c < N;c++)
{
// if the value of the coin is less than the amount
if(coins[c] <= amt)
{
// What is the other number of coins that will be used
// if coins[c] is used in the solution for amount i
int temp_amt = amount[amt-coins[c]] + 1;

// choose the minimum number of coins that will be used
// for the amount i

if(temp_amt < temp)
{
temp = temp_amt;
amount[amt] = temp;
}
}
}
}
cout << amount[C] << endl;
return 0;
}

News Reporter

Leave a Reply

Your email address will not be published. Required fields are marked *