|
|
| 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!")
| + | Back to [[Chapter 9]] |
| − | 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]] | |
