document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. /**
  2.  * The coin change problem is an unbounded knapsack problem variant. The problem asks you to find
  3.  * the minimum number of coins required for a certain amount of change given the coin denominations.
  4.  * You may use each coin denomination as many times as you please.
  5.  *
  6.  * <p>Tested against: https://leetcode.com/problems/coin-change/
  7.  *
  8.  * @author William Fiset, william.alexandre.fiset@gmail.com
  9.  */
  10. import java.util.*;
  11.  
  12. public class CoinChange {
  13.  
  14.   private static final int INF = 987654321;
  15.  
  16.   public static int coinChange(int[] coins, int amount) {
  17.  
  18.     if (coins == null) throw new IllegalArgumentException("Coins array is null");
  19.     if (coins.length == 0) throw new IllegalArgumentException("No coin values :/");
  20.  
  21.     final int N = coins.length;
  22.     // Initialize table and set first row to be infinity
  23.     int[][] DP = new int[N + 1][amount + 1];
  24.     java.util.Arrays.fill(DP[0], INF);
  25.     DP[1][0] = 0;
  26.  
  27.     // Iterate through all the coins
  28.     for (int i = 1; i <= N; i++) {
  29.  
  30.       int coinValue = coins[i - 1];
  31.       for (int j = 1; j <= amount; j++) {
  32.  
  33.         // Consider not selecting this coin
  34.         DP[i][j] = DP[i - 1][j];
  35.  
  36.         // Try selecting this coin if it\'s better
  37.         if (j - coinValue >= 0 && DP[i][j - coinValue] + 1 < DP[i][j])
  38.           DP[i][j] = DP[i][j - coinValue] + 1;
  39.       }
  40.     }
  41.  
  42.     // The amount we wanted to make cannot be made :/
  43.     if (DP[N][amount] == INF) return -1;
  44.  
  45.     // Return the minimum number of coins needed
  46.     return DP[N][amount];
  47.   }
  48.  
  49.   public static int coinChangeSpaceEfficient(int[] coins, int amount) {
  50.  
  51.     if (coins == null) throw new IllegalArgumentException("Coins array is null");
  52.  
  53.     // Initialize table and set everything to infinity except first cell
  54.     int[] DP = new int[amount + 1];
  55.     java.util.Arrays.fill(DP, INF);
  56.     DP[0] = 0;
  57.  
  58.     for (int i = 1; i <= amount; i++)
  59.       for (int coinValue : coins)
  60.         if (i - coinValue >= 0 && DP[i - coinValue] + 1 < DP[i]) DP[i] = DP[i - coinValue] + 1;
  61.  
  62.     // The amount we wanted to make cannot be made :/
  63.     if (DP[amount] == INF) return -1;
  64.  
  65.     // Return the minimum number of coins needed
  66.     return DP[amount];
  67.   }
  68.  
  69.   // The recursive approach has the advantage that it does not have to visit
  70.   // all possible states like the tabular approach does. This can speedup
  71.   // things especially if the coin denominations are large.
  72.   public static int coinChangeRecursive(int[] coins, int amount) {
  73.  
  74.     if (coins == null) throw new IllegalArgumentException("Coins array is null");
  75.     if (amount < 0) return -1;
  76.  
  77.     int[] DP = new int[amount + 1];
  78.     return coinChangeRecursive(amount, coins, DP);
  79.   }
  80.  
  81.   // Private helper method to actually go the recursion
  82.   private static int coinChangeRecursive(int amount, int[] coins, int[] DP) {
  83.  
  84.     // Base cases.
  85.     if (amount < 0) return -1;
  86.     if (amount == 0) return 0;
  87.     if (DP[amount] != 0) return DP[amount];
  88.  
  89.     int minCoins = INF;
  90.     for (int coinValue : coins) {
  91.  
  92.       int newAmount = amount - coinValue;
  93.       int value = coinChangeRecursive(newAmount, coins, DP);
  94.       if (value != -1 && value < minCoins) minCoins = value + 1;
  95.     }
  96.  
  97.     // If we weren\'t able to find some coins to make our
  98.     // amount then cache -1 as the answer.
  99.     return DP[amount] = (minCoins == INF) ? -1 : minCoins;
  100.   }
  101.  
  102.   public static void main(String[] args) {
  103.       Scanner input = new Scanner(System.in);
  104.  
  105.       System.out.print("Total Coins: ");
  106.       int totalCoins = input.nextInt();
  107.      
  108.       int[] coins = new int[totalCoins];
  109.       System.out.print("Coin denomination: ");
  110.       for(int i = 0; i < totalCoins; i++)
  111.       {
  112.           try{
  113.                 coins[i] = input.nextInt();
  114.             }
  115.             catch(InputMismatchException e){
  116.                 System.out.println("Input not recognized");
  117.                 break;
  118.             }
  119.             catch(ArrayIndexOutOfBoundsException e){
  120.                 System.out.println("Coins Total is out of bounds");
  121.             }
  122.             catch(Exception e){
  123.                 throw new IllegalArgumentException(e);
  124.             }
  125.       }
  126.      
  127.       try{
  128.           System.out.print("Change given: ");
  129.           int amount = input.nextInt();
  130.          
  131.           System.out.println("Minimum coins needed");
  132.           System.out.printf("a. First solution: %d\\n", coinChange(coins, amount));
  133.           System.out.printf("b. Space efficient solution: %d\\n",
  134.             coinChangeSpaceEfficient(coins, amount));
  135.           System.out.printf("c. Recursive solution: %d\\n",
  136.             coinChangeRecursive(coins, amount));
  137.         }
  138.         catch(InputMismatchException e){
  139.             throw new InputMismatchException("Input not recognized");
  140.         }
  141.         finally{
  142.             System.out.println("Program Finished");
  143.         }
  144.   }
  145. }
');