Algowikiadmin: Recovering wiki

2014-09-11T18:24:12Z

Recovering wiki

New page

== 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]

TADM2E 8.24 - Revision history

Algowikiadmin: Recovering wiki