Difference between pages "10.41" and "10.39"
(Difference between pages)
Jump to navigation
Jump to search
(Created page with " Back to Chapter 10") |
(Created page with "== A Python Solution - O(1) == <PRE> import sys n = int(sys.argv[1]) OUT_TMP = "Min # of coins for covering %d: %d, coins used: %s" COINS = tuple(sorted((3, 4, 9, 20, 22, 23)...") |
||
Line 1: | Line 1: | ||
+ | == A Python Solution - O(1) == | ||
+ | <PRE> | ||
+ | import sys | ||
+ | n = int(sys.argv[1]) | ||
+ | |||
+ | OUT_TMP = "Min # of coins for covering %d: %d, coins used: %s" | ||
+ | COINS = tuple(sorted((3, 4, 9, 20, 22, 23), reverse=True)) | ||
+ | FAILSAFE_MAX = 9999999999 | ||
+ | |||
+ | if len(COINS) < 1: raise Exception("Coins please!") | ||
+ | if len(COINS) == 1: | ||
+ | c = COINS[0] | ||
+ | if n % c == 0: | ||
+ | print OUT_TMP % (n, n/c, [c]*(n/c)) | ||
+ | sys.exit() | ||
+ | else: | ||
+ | raise Exception("Impossible!") | ||
+ | |||
+ | CAL_MAX = min(COINS[0] * COINS[1], n+1) | ||
+ | |||
+ | min_coins_n = [0] | ||
+ | min_coins_l = [()] | ||
+ | |||
+ | for i in xrange(1, CAL_MAX): | ||
+ | if i in COINS: | ||
+ | min_coins_n.append(1) | ||
+ | min_coins_l.append((i,)) | ||
+ | else: | ||
+ | current_min = -1 | ||
+ | for c in COINS: | ||
+ | smaller_i = i - c | ||
+ | if smaller_i > 0 and min_coins_n[smaller_i] < FAILSAFE_MAX and \ | ||
+ | (current_min == -1 or min_coins_n[smaller_i] < min_coins_n[current_min]): | ||
+ | current_min = smaller_i | ||
+ | |||
+ | if current_min != -1: | ||
+ | min_coins_n.append(min_coins_n[current_min] + 1) | ||
+ | l = list(min_coins_l[current_min]) # copy | ||
+ | l.append(i - current_min) | ||
+ | # another copy, not required but robuster code | ||
+ | ll = tuple(l) | ||
+ | min_coins_l.append(tuple(l)) | ||
+ | else: | ||
+ | # not changable using the current coins | ||
+ | min_coins_n.append(FAILSAFE_MAX) | ||
+ | min_coins_l.append(None) | ||
+ | |||
+ | big_part_n = 0 | ||
+ | coins_list = [] | ||
+ | remaining_n = n | ||
+ | if n > CAL_MAX: | ||
+ | n_big_part = n - CAL_MAX | ||
+ | big_part_n = (n_big_part / COINS[0]) + 1 | ||
+ | coins_list = [COINS[0]] * big_part_n | ||
+ | remaining_n -= big_part_n * COINS[0] | ||
+ | |||
+ | final_n = big_part_n + min_coins_n[remaining_n] | ||
+ | if final_n >= FAILSAFE_MAX: | ||
+ | raise Exception("Impossible!") | ||
+ | coins_list.extend(min_coins_l[remaining_n]) | ||
+ | print OUT_TMP % (n, final_n, coins_list) | ||
+ | </PRE> | ||
+ | |||
+ | == A Java solution - O(n) == | ||
+ | |||
+ | <PRE> | ||
+ | |||
+ | public class CoinProblem { | ||
+ | |||
+ | public static void main(String[] args) { | ||
+ | int sumToMakeChangeFor = 20; | ||
+ | int[] coinDenominations = new int[]{1, 2, 5, 10}; | ||
+ | |||
+ | System.out.println("Number of coins needed = " + numberOfCoinsNeededForChange(sumToMakeChangeFor, coinDenominations)); | ||
+ | } | ||
+ | |||
+ | private static int numberOfCoinsNeededForChange(int sum, int[] coinDenominations) { | ||
+ | int[] minimumNumberOfCoinsNeeded = new int[sum + 1]; | ||
+ | for (int i = 0; i <= sum; i++){ | ||
+ | minimumNumberOfCoinsNeeded[i] = Integer.MAX_VALUE; | ||
+ | } | ||
+ | minimumNumberOfCoinsNeeded[0] = 0; | ||
+ | |||
+ | for (int currentSum = 1; currentSum <= sum; currentSum++) { | ||
+ | for (int j = 0; j < coinDenominations.length; j++) { | ||
+ | if (coinDenominations[j] <= currentSum && | ||
+ | ((minimumNumberOfCoinsNeeded[currentSum - coinDenominations[j]] + 1) < minimumNumberOfCoinsNeeded[currentSum])) | ||
+ | minimumNumberOfCoinsNeeded[currentSum] = minimumNumberOfCoinsNeeded[currentSum - coinDenominations[j]] + 1; | ||
+ | } | ||
+ | } | ||
+ | return minimumNumberOfCoinsNeeded[sum]; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | |||
+ | |||
+ | </PRE> | ||
+ | |||
+ | Reference: [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg Dynamic Programming, TopCoder.com] | ||
Back to [[Chapter 10]] | Back to [[Chapter 10]] |
Latest revision as of 13:49, 21 September 2020
A Python Solution - O(1)
import sys n = int(sys.argv[1]) OUT_TMP = "Min # of coins for covering %d: %d, coins used: %s" COINS = tuple(sorted((3, 4, 9, 20, 22, 23), reverse=True)) FAILSAFE_MAX = 9999999999 if len(COINS) < 1: raise Exception("Coins please!") if len(COINS) == 1: c = COINS[0] if n % c == 0: print OUT_TMP % (n, n/c, [c]*(n/c)) sys.exit() else: raise Exception("Impossible!") CAL_MAX = min(COINS[0] * COINS[1], n+1) min_coins_n = [0] min_coins_l = [()] for i in xrange(1, CAL_MAX): if i in COINS: min_coins_n.append(1) min_coins_l.append((i,)) else: current_min = -1 for c in COINS: smaller_i = i - c if smaller_i > 0 and min_coins_n[smaller_i] < FAILSAFE_MAX and \ (current_min == -1 or min_coins_n[smaller_i] < min_coins_n[current_min]): current_min = smaller_i if current_min != -1: min_coins_n.append(min_coins_n[current_min] + 1) l = list(min_coins_l[current_min]) # copy l.append(i - current_min) # another copy, not required but robuster code ll = tuple(l) min_coins_l.append(tuple(l)) else: # not changable using the current coins min_coins_n.append(FAILSAFE_MAX) min_coins_l.append(None) big_part_n = 0 coins_list = [] remaining_n = n if n > CAL_MAX: n_big_part = n - CAL_MAX big_part_n = (n_big_part / COINS[0]) + 1 coins_list = [COINS[0]] * big_part_n remaining_n -= big_part_n * COINS[0] final_n = big_part_n + min_coins_n[remaining_n] if final_n >= FAILSAFE_MAX: raise Exception("Impossible!") coins_list.extend(min_coins_l[remaining_n]) print OUT_TMP % (n, final_n, coins_list)
A Java solution - O(n)
public class CoinProblem { public static void main(String[] args) { int sumToMakeChangeFor = 20; int[] coinDenominations = new int[]{1, 2, 5, 10}; System.out.println("Number of coins needed = " + numberOfCoinsNeededForChange(sumToMakeChangeFor, coinDenominations)); } private static int numberOfCoinsNeededForChange(int sum, int[] coinDenominations) { int[] minimumNumberOfCoinsNeeded = new int[sum + 1]; for (int i = 0; i <= sum; i++){ minimumNumberOfCoinsNeeded[i] = Integer.MAX_VALUE; } minimumNumberOfCoinsNeeded[0] = 0; for (int currentSum = 1; currentSum <= sum; currentSum++) { for (int j = 0; j < coinDenominations.length; j++) { if (coinDenominations[j] <= currentSum && ((minimumNumberOfCoinsNeeded[currentSum - coinDenominations[j]] + 1) < minimumNumberOfCoinsNeeded[currentSum])) minimumNumberOfCoinsNeeded[currentSum] = minimumNumberOfCoinsNeeded[currentSum - coinDenominations[j]] + 1; } } return minimumNumberOfCoinsNeeded[sum]; } }
Reference: Dynamic Programming, TopCoder.com
Back to Chapter 10