For the sake of learning, I want to solve [problem 31] (https://projecteuler.net/problem=31) on Project Euler using top-down DP. I have already solved it using both brute force and bottom-up Dynamic Programming.
Problem summary: Number of unique combinations (order doesn't matter) in which sums to £2, having the coins 1p, 2p, 5p, 10p, 20p, 50p, £1, £2.
I have done several attempts, but my result does take order into account. I tried to exclude this by including an "upperLimit" variable, whose job is to never include a more valuable coin (eliminating possibilities like 5,1,2,1, instead of 5,2,1,1)
However, it still doesn't yield correct results. This is my code, and below the TOP DOWN I've included the bottom-up approach which works.
Lets simplify for 5p instead of 200p, with the coins 1,2,5. This should yield 4 combinations: 5, 221, 2111, 11111.
My code with top-down outputs 5 combinations, while the bottom up correctly outputs 4.
TOP-DOWN APPROACH (doesn't work yet)
combos = [0 for x in range(0,201)]
def combinations(currentValue, upperLimit = 200):
#Reset counter
numbOfCombos = 0
#If we reach leaf
if currentValue == 0:
return 1
#If the value is already known, return it
elif combos[currentValue] != 0:
return combos[currentValue]
#Else recurse through the tree
else:
if currentValue >= 200:
numbOfCombos = numbOfCombos combinations(currentValue-200, 200)
if currentValue >= 100 and upperLimit >= 100:
numbOfCombos = numbOfCombos combinations(currentValue-100, 100)
if currentValue >= 50 and upperLimit >= 50:
numbOfCombos = numbOfCombos combinations(currentValue-50, 50)
if currentValue >= 20 and upperLimit >= 20:
numbOfCombos = numbOfCombos combinations(currentValue-20, 20)
if currentValue >= 10 and upperLimit >= 10:
numbOfCombos = numbOfCombos combinations(currentValue-10, 10)
if currentValue >= 5 and upperLimit >= 5:
numbOfCombos = numbOfCombos combinations(currentValue-5, 5)
if currentValue >= 2 and upperLimit >= 2:
numbOfCombos = numbOfCombos combinations(currentValue-2, 2)
if currentValue >= 1 and upperLimit >= 1:
numbOfCombos = numbOfCombos combinations(currentValue-1, 1)
combos[currentValue] = numbOfCombos
return combos[currentValue]
print(combinations(5,))
BOTTOM-UP APPROACH (works)
targetValue = 200;
coins = [1, 2, 5, 10, 20, 50, 100, 200];
combinations = [0 for x in range(0,targetValue 1)];
combinations[0] = 1;
for i in range(0, len(coins)):
for j in range(coins[i], targetValue 1):
combinations[j] = combinations[j] combinations[j - coins[i]];
print(combinations);
Output
Any tips/advice or complete solutions are greatly appreciated. I know that the bottom-up solution is probably the most efficient and most beautiful, but for the sake of learning thought processes I'd like to solve it using TOP-DOWN.
Thanks!
CodePudding user response：
It’s counting 1,1,2,1 because when it’s counting solutions with 2,*, it memoizes 2 solutions for 3p, then counts 2 solutions for 1,1,*.
The fix is to include upperLimit in the memoization. (I also added a
missing test upperLimit >= 200.) See below.
combos = {}
def combinations(currentValue, upperLimit=200):
# Reset counter
numbOfCombos = 0
# If we reach leaf
if currentValue == 0:
return 1
# If the value is already known, return it
elif (currentValue, upperLimit) in combos:
return combos[currentValue, upperLimit]
# Else recurse through the tree
else:
if currentValue >= 200 and upperLimit >= 200:
numbOfCombos = numbOfCombos combinations(currentValue - 200, 200)
if currentValue >= 100 and upperLimit >= 100:
numbOfCombos = numbOfCombos combinations(currentValue - 100, 100)
if currentValue >= 50 and upperLimit >= 50:
numbOfCombos = numbOfCombos combinations(currentValue - 50, 50)
if currentValue >= 20 and upperLimit >= 20:
numbOfCombos = numbOfCombos combinations(currentValue - 20, 20)
if currentValue >= 10 and upperLimit >= 10:
numbOfCombos = numbOfCombos combinations(currentValue - 10, 10)
if currentValue >= 5 and upperLimit >= 5:
numbOfCombos = numbOfCombos combinations(currentValue - 5, 5)
if currentValue >= 2 and upperLimit >= 2:
numbOfCombos = numbOfCombos combinations(currentValue - 2, 2)
if currentValue >= 1 and upperLimit >= 1:
numbOfCombos = numbOfCombos combinations(currentValue - 1, 1)
combos[currentValue, upperLimit] = numbOfCombos
return numbOfCombos
print(combinations(5))
CodePudding user response：
Posted top down approach can be simplified (i.e. less conditionals) and generalized to any set of coins using Coin Change | DP-7
For a set of coin S, we split the solution space into two sets:
- Solutions that do not contain mth coin (or S[m).
- Solutions that contain at least one S[m]. Let count(S, m, target) be the function to count the number of solutions, then it can be written as sum of count(S, m-1, target) and count(S, m, target-S[m]).
Code
def count(S, target):
'''
Returns the count of ways we can sum
S[0...m-1] coins to get sum target
'''
def recur(m, target):
# Helper function to enable Memoization
# If target is 0 then there is 1
# solution (do not include any coin)
if (target == 0):
return 1
# target < 0 -> no solution exists
if (target < 0):
return 0
# no coins and target > 0 -> no solution
if (m <=0 and target > 0):
return 0
# Check if coin combination and target amount have been solved before
if (m, target) in lookup:
return lookup[(m, target)]
# sum of two solutions:
# 1. does not use m coin i.e. recur (m-1, target)
# 2. uses at least one of m-th coin i.e. recur(m, target - S[m-1])
# including S[m-1] (ii) excluding S[m-1]
lookup[(m, target)] = recur(m - 1, target ) recur(m, target - S[m-1])
return lookup[(m, target)]
lookup = {}
return recur(len(S), target)
Test
arr = [1, 2, 5, 10, 20, 50, 100, 200]
print(count(arr, 200))
# Output: 73682