Minimum Coin Change Print All Combinations

Question

Given an array of coin denominations coins and a total, find all possible combinations that result in the minimum number of coins summing to the total. In my solution I keep a running track of the minimum number of coins at table[i] that sum to i. I'm not sure exactly how this would be modified to store the actual coins that sum to i and make sure that both possibilities in this case are included. I've looked at other code on stack overflow, but I've only found code that will print any one of the optimal solutions.

Input: minimum_coins(10, [2,3,5,6,7,8])
Output: [[5,5],[2,8]]

INT_MAX = 2 ** 63 - 1
def minimum_coins(total, coins)
  table = Array.new(total + 1)
  table[0] = 0

  (1..total).to_a.each do |i|
    table[i] = INT_MAX
  end

  (1..total).to_a.each do |i|
    (0..coins.length-1).to_a.each do |j|
      if coins[j] <= i
        sub_res = table[i-coins[j]]
        if sub_res != INT_MAX && sub_res + 1 < table[i]
          table[i] = sub_res + 1
        end
      end
    end
  end
  puts table.inspect
end

minimum_coins(10, [2,3,5,6,7,8])

Answer 1

Let's table entries contain pairs (BestCount, LastCoinList).

If sub_res + 1 < table[i].BestCount then replace BestCount with sub_res + 1 and make LastCoinList containing coins[j] value

If sub_res + 1 = table[i].BestCount then just add coins[j] value to LastCoinList

So in the end table[10] will contain BestValue = 2 and LastCoinList = (5,7,8)

Now recursively unroll from table[10] entry to table[10-5], to table[10-7], to table[10-8], that contain 5,3 and 2 respectively, then all recursion branches stop at the 0th entry.

Answer 2

let:

d[i] = minimum changes for i

So if d[i] == d[i - c] + 1, we can say if we take coin c to make exchange and we can still get a minimum coin changes for i.

Code:

def find(n, result, d, coins, changes, index):
    if n == 0:
        changes.append(result)
        return
    for i in range(index, len(coins)):
        if n - coins[i] >= 0 and d[n] == d[n - coins[i]] + 1:
            find(n - coins[i], result + [coins[i]], d, coins, changes, i)


def all_coin_changes(n, coins):
    d = [n + 1] * (n + 1)
    d[0] = 0
    for i in range(1, n + 1):
        for c in coins:
            if i - c >= 0:
                d[i] = min(d[i], d[i - c] + 1)
    changes = []
    find(n, [], d, coins, changes, 0)
    return changes

print all_coin_changes(10, [2, 3, 5, 6, 7, 8]) 
# [[2, 8], [3, 7], [5, 5]]
print all_coin_changes(100, [2, 3, 5, 6, 7, 8]) 
# [[5, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8], [6, 6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8], [6, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8], [7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8]]

If you still have some questions, please don't hesitate to leave a comment here.

Answer 3

I made an iterative program that can calculate the minimum number of coins required (US dollars) to get a given number of cents. It's iterative, but hope it helps!

import java.util.*;
public class CoinProblem
{
public static void main(String[] args)
{
  System.out.println("----------------------------COIN PROBLEM--------------------------");
  System.out.println("Denominations: \nCent - 1\nNickel - 5\nDime - 10\nQuarter - 25");
  Map<Integer, Integer> map = new HashMap<Integer, Integer> ();
  System.out.println("\nENTER TARGET NUMBER (CENTS): ");
  Scanner sc = new Scanner(System.in);
  int target = Integer.parseInt(sc.next());
  int count = numCoins(target, map);
  System.out.println("\nMINIMUM NUMBER OF COINS REQUIRED: " + count);
  System.out.println( map.get(1) + " CENTS");
  System.out.println( map.get(5) + " NICKELS"); 
  System.out.println( map.get(10) + " DIMES");
  System.out.println( map.get(25) + " QUARTERS");
  System.out.println("------------------------------------------------------------------");    
}
public static int numCoins(int target, Map<Integer, Integer> map)
{
  int cent = 1;
  int nickel = 5;
  int dime = 10;
  int quarter = 25;
  map.put(cent, 0);
  map.put(nickel, 0);
  map.put(dime, 0);
  map.put(quarter, 0);
  int count = 0;
  if (target >= 25)
  {
     if (target % 25 == 0)
     {
        count += target/25;
        map.put(quarter, count);
        return count;
     }
     else
     {
        count += target/25;
        map.put(quarter, count);
        int remtarget = target%25;
        if (remtarget >= 10)
        {
           if (remtarget %  10 == 0)
           {
              count += remtarget/10;
              map.put(dime, remtarget/10);
              return count;
           }
           else
           {
              count += remtarget/10;
              map.put(dime, remtarget/10);
              int fivetarget = remtarget%10;
              if (fivetarget >= 5)
              {
                 if (fivetarget % 5 == 0)
                 {
                    count += fivetarget/5;
                    map.put(nickel, fivetarget/5);
                 }
                 else
                 {
                    count += fivetarget/5;
                    map.put(nickel, fivetarget/5);
                    int ones = fivetarget%5;
                    count+= ones;
                    map.put(cent, ones);
                 }
              }
              else
              {
                 count += fivetarget;
                 map.put(cent, fivetarget);
                 return count;
              }
           }
        }
        else
        {
           if (remtarget >= 5)
           {
              if (remtarget % 5 == 0)
              {
                 count += remtarget/5;
                 map.put(nickel, remtarget/5);
              }
              else
              {
                 count += remtarget/5;
                 map.put(nickel, remtarget/5);
                 int ones = remtarget%5;
                 count+= ones;
                 map.put(cent, ones);
              }
           }
           else
           {
              count += remtarget;
              map.put(cent, remtarget);
              return count;
           }

        }
     }
  }
  else
  {
     if (target == 0)
     {
        return 0;
     }
     if (target >= 10)
     {
        if (target %  10 == 0)
        {
           count += target/10;
           map.put(dime, target/10);
           return count;
        }
        else
        {
           count += target/10;
           map.put(dime, target/10);
           int ftarget = target%10;           
           if (ftarget >= 5)
           {
              if (ftarget % 5 == 0)
              {
                 count += ftarget/5;
                 map.put(nickel, ftarget/5);
              }
              else
              {
                 count += ftarget/5;
                 map.put(nickel, ftarget/5);
                 int otarget = ftarget%5;
                 count+= otarget;
                 map.put(cent, otarget);
              }
           }
           else
           {
              count += ftarget;
              map.put(cent, ftarget);
              return count;
           }
        }
     }
     else
     {  
        if (target > 5)
        {
           if (target % 5 == 0)
           {
              count += target/5;
              map.put(nickel, target/5);
           }
           else
           {
              count += target/5;
              map.put(nickel, target/5);
              int o = target%5;
              count+= o;
              map.put(cent, o);
           }
        }
        else
        {
           count += target;
           map.put(cent, target);
           return count;
        }
     }
  }
  return count;
 }
 }