Coin change DP solution to keep track of coins

Question

Trying to program a DP solution for the general coin-change problem that also keeps track of which coins are used. So far I have it working to give me the minimum amount of coins needed but can't figure out how to get which coins were used and how many times. I tried setting up another table (boolean) with values if the coin is used but that doesn't seem to work correctly. Any ideas?

public static int minChange(int[] denom, int changeAmount) 
{   
    int m = denom.length;
    int n = changeAmount + 1;

    int[][] table = new int[m][n];
    boolean[][] used = new boolean[m][n];
    for (int j = 0; j < n; j++)
        table[m - 1][j] = j;
    for (int i = 0; i < m; i++)
        table[i][0] = 0;

    for (int i = m-2; i >= 0; i--) //i denotes denominationIndex
    {
        for (int j = 1; j < n; j++) //j denotes current Amount
        {
            if (denom[i] > j)
            {
                table[i][j] = table[i+1][j];
                //used[i][j] = false;
            }
            else
            {
                table[i][j] = Math.min(1 + table[i][j-denom[i]], table[i+1][j]);
                /*Trying table for used coins
                if (1 + table[i][j-denom[i]] < table[i+1][j]) 
                    used[i][j] = true;
                else
                    used[i][j] = false;
                */
            }
        }
    }
}

When asking a question, _"doesn't work correctly"_ is usually insufficient. Please explain what happens and how that differs from what you expect. — Jim Garrison, Nov 25 '13 at 06:23
When I say it doesn't work correctly what I mean is that the table is giving me true in areas that aren't part of the minimum coin answer. For example, if I run it using 4 coins of denomination 10, 7, 6, 1 for a change total of 14, the boolean table is giving me true for 7 and 6 when it should only be giving me true for the 7. — Javier Garrido, Nov 25 '13 at 06:27
table[i][j] refers to the table I am using to store the minimum amount of coins used during the dynamic programming. After the program runs it would point to the correct minimum amount of coins needed. — Javier Garrido, Nov 25 '13 at 06:30
@JavierGarrido I meant, what do i and j denote in this table? — Abhishek Bansal, Nov 25 '13 at 06:34
i denotes the location in denom[] indicating what values of coins we can use. j denotes the amount of change that we need to make — Javier Garrido, Nov 25 '13 at 06:40

score 6 · Answer 1 · answered Nov 25 '13 at 08:02

Try this solution, it used only O(M) memory and has O(N*M) complexity:

   public static int[] minChange(int[] denom, int changeAmount)
    {
        int n = denom.length;
        int[] count = new int[changeAmount + 1];
        int[] from = new int[changeAmount + 1];

        count[0] = 1;
        for (int i = 0 ; i < changeAmount; i++)
            if (count[i] > 0)
                for (int j = 0; j < n; j++)
                {
                    int p = i + denom[j];
                    if (p <= changeAmount)
                    {
                        if (count[p] == 0 || count[p] > count[i] + 1)
                        {
                            count[p] = count[i] + 1;
                            from[p] = j;
                        }
                    }
                }

        // No solutions:
        if (count[changeAmount] == 0)
            return null;

        // Build answer.
        int[] result = new int[count[changeAmount] - 1];
        int k = changeAmount;
        while (k > 0)
        {
            result[count[k] - 2] = denom[from[k]];
            k = k - denom[from[k]];
        }

        return result;
    }

what is M in complexity? – Dinuka Thilanga May 29 '15 at 17:12 — Dinuka Thilanga, May 29 '15 at 17:12

score 5 · Answer 2 · answered Apr 21 '15 at 13:29

public static int minimumNumberOfWays(int []deno, int amount){
    int dp[] = new int[amount+1];
    dp[0]=0;
    int []prevCoin = new int[amount+1];  
    for(int j=1;j<=amount;j++){
        dp[j]=Integer.MAX_VALUE;
        for(int i=0;i<deno.length;i++){
            if(deno[i]<=j && (1+dp[j-deno[i]] < dp[j]) ){               
                dp[j]=1+dp[j-deno[i]];
                prevCoin[j]=deno[i];
            }                   
        }
    }

    int result = dp[amount];
    List<Integer> coinsAdded = new ArrayList<Integer>();
    for(int i=amount;i>=1;){
        coinsAdded.add(prevCoin[i]);
        int j=i;
        i=amount-prevCoin[i];
        amount = amount - prevCoin[j];
    }
    Integer [] coins = coinsAdded.toArray(new Integer[coinsAdded.size()]);
    System.out.println( Arrays.toString(coins));

score 1 · Answer 3 · answered Nov 25 '13 at 12:01

Use following pseudo code for reconstructing solution : -

solutionSet = []

i = denom.length-1

j = changeAmount

While(i>=0) {

   if(1+table[i][j-denom[i]]<table[i+1][j]) {
         solutionSet.add(denom[i])
         j = j - denom[i]
     }
   i--
}

Note: There is no need to use extra memory here other than needed to store the solution

score 0 · Answer 4 · answered Nov 25 '13 at 06:31

The following seems to work in Python:

def g( A, n ) :
    #
    if A == [] or n == 0 or min(A) > n :
        return []

    #
    else :

        #
        min_len = float( "inf" )
        min_seq = None

        #
        for i, a in enumerate( A ) :
            if a <= n :
                #
                tmp = [ a ] + g( A[:i] + A[i+1:], n-a )

                #
                if len( tmp ) < min_len :
                    min_seq = tmp
                    min_len = len( min_seq )
        #
        return min_seq


#
for i in xrange(20) :
    #
    A = list( nr.randint( 1, 10, 5 ) )
    print A, g( A[:-1], A[-1] )

score 0 · Answer 5 · answered Nov 25 '13 at 07:58

You don't need the first dimension of your dp. You can use an array with only one dimension - the sum of all used coins. Then you can simply store the index of your last used coin for each state of your dp. What I mean is something like:

int[] dp = new int[n];
int[] usedCoin = new int[n];

for (int i=0; i < n; ++i) {
    dp[i] = -1; // state not reached
    usedCoin[i] = -1;
}

dp[0] = 0; // initial state -- we can have sum 0 without any coins
for (int coinId = 0; coinId < m; coinId++)
    for (int sum = 0; sum + denom[coinId] < n; sum++) {
        int newSum = sum + denom[coinId];
        if (dp[newSum] == -1 || dp[newSum] > 1 + dp[sum]) {
            dp[newSum] = 1 + dp[sum];
            usedCoin[newSum] = coinId;
        }
    }

If you want to find a concrete decomposition with minimum amount of coins, you can do something like:

int sum = changeAmount;
System.out.println("The used coins are:");
while (usedCoin[sum] != -1) {
    System.out.print(denom[ usedCoin[sum] ].toString() + " ");
    sum -= denom[ usedCoin[sum] ];
}

score 0 · Answer 6 · edited May 14 '15 at 14:50

public class CoinChange {

    public static void main(String[] args) {
        int[] coins = {1,2,10,5};       
        int amt = 37;       
        makeChange(coins, amt); 
    }

    public static void makeChange(int[] coins, int amount){
        //Sorting the coins
        Arrays.sort(coins);

        int n = coins.length - 1;


        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        while(amount > 0)
        {
            if(coins[n] <= amount)
            {
                int val = 1;
                if(map.containsKey(coins[n]))
                {
                    val = map.get(coins[n]);
                    val = val+1;
                }

                map.put(coins[n], val);

                amount = amount - coins[n];

            }
            else
            {
                n--;
            }

        }

        for(Map.Entry<Integer, Integer> entry: map.entrySet()){

            System.out.println(entry.getKey() +":" + entry.getValue());
        }
    }
}

This is a greedy approach, not DP! Greedy does not always find the optimal solution. — Vetterjack, Dec 12 '18 at 15:12

score 0 · Answer 7 · answered Dec 30 '15 at 10:37

public class CoinChange {
/**
 * Get mini num of coins
 * 
 * @param coinValues
 *            coins
 * @param totalMoney
 *            total money
 * @return
 */
public int coinNum(int[] coinValues, int totalMoney) {
    List<Integer> coins = new ArrayList<Integer>();
    coins.add(0);
    for (int i = 1; i <= totalMoney; i++) {
        int coin = nearestCoin(i, coinValues);
        int coinNum = coins.get(i - coin) + 1;
        coins.add(coinNum);
    }
    return coins.get(totalMoney);
}

/**
 * Get the coin nearest to specified value.
 */
private int nearestCoin(int value, int[] coinValues) {
    int res = 0;
    int nearest = Integer.MAX_VALUE;
    for (int coinValue : coinValues) {
        if (coinValue <= value) {
            int distance = value - coinValue;
            if (distance < nearest) {
                nearest = distance;
                res = coinValue;
            }
        }
    }
    return res;
}

@Test
public void test() throws Exception {
    int res = coinNum(new int[] { 1, 2, 3, 5, 11 }, 81);
    System.out.println(res);
}

}

score 0 · Answer 8 · answered Aug 05 '17 at 17:27

/* Coin Change Problem

Input Specification: First Line expects the amount Second Line expects the number of coins Third Line contains coins in ascending order of denominations Infinite Supply Of Coins is assumed

Ouput Specification: Each case is displayed with the lowest denomination coin first then the next highest denomination. Cases are separated by lines If amount cannot be formed -1 is printed NOTE:This is not a DP Solution */

#include<iostream>
using namespace std;
int *num,*coins,*maxC,n,amount,flag=0,stop=0;
int sum()
{
    int i=0,j;
    int sum=0;
    for(i=0;i<n;++i)
        for(j=0;j<num[i];++j)
            sum+=coins[i];
    return sum;
}
void print()
{
    int i,j;
    for(i=0;i<n;++i)
    {
        for(j=0;j<num[i];++j)
            cout<<coins[i]<<" ";
    }
    cout<<endl;
}
void printNum()
{
    int i;
    for(i=0;i<n;++i)
        cout<<num[i]<<" ";
    cout<<endl;
}
void nextIter()
{
    int i,j;
    int stat=0;
    //printNum();   //Remove the comment if you want to see the values of num array in every iteration
    for(i=0;i<n;++i)
    {
        if(num[i]==0)
            stat=1;
        else
        {
            stat=0;
            break;
        }
    }
    if(stat)
    {
        stop=1;
        return ;
    }
    for(i=n-1;i>=0;--i)
    {
        int dec=0;
        if(num[i]==0)
        {
            dec=1;
            num[i]=maxC[i];
        }
        else
        {
            --num[i];
            return ;
        }
    }
}
int find()
{
    while(!stop)
    {
        if(amount==sum())
        {
            flag=1;
            print();
        }
        nextIter();
    }
}
int main()
{
    int i;
    cout<<"\nEnter amount:";
    cin>>amount;
    cout<<"\nEnter number of coins:";
    cin>>n;
    coins=new int[n];
    maxC=new int[n];//contains maximum number of each denomination required
    num=new int[n];//contains current number of each denomination required
    for(i=0;i<n;++i)
    {
        cin>>coins[i];
        num[i]=maxC[i]=amount/coins[i];
    }
    find();
    if(!flag)
        cout<<"-1";
    cout<<endl;
    system("pause");
    return 0;
}

Shubham Yadav · Answer 9 · 2019-02-10T12:19:53.523

-1

Solution using Dynamic Programming ::

public int coinchange2(ArrayList<Integer> A, int B) {
    int[] dp = new int[B+1];

    dp[0]=1;

    for(int i=0;i<A.size();i++){
        for(int j=A.get(i);j<=B;j++)
        {
            dp[j]=(dp[j]+dp[j-A.get(i)])%1000007;
        }
    }
    return dp[B];
}

edited Feb 10 '19 at 12:19

answered Feb 09 '19 at 11:32

Shubham Yadav

1
3

While this code snippet may solve the question, [including an explanation](http://meta.stackexchange.com/questions/114762/explaining-entirely-code-based-answers) really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion. – Jeroen Steenbeeke May 20 '21 at 06:31

Coin change DP solution to keep track of coins

9 Answers9

Linked