I found this answer on stackoverflow Algorithm to find which number in a list sum up to a certain number
I am struggling to learn dynamic programming and finding it a challenge to follow the logic. I tried changing S==0 to other values but this did not produce the desired results.
Is it possible to modify this code so the numbers don't have to sum exactly to the total, ie allow a small difference to deal with rounding issues.
def f(v, i, S, memo):
if i >= len(v): return 1 if S == 0 else 0
if (i, S) not in memo: # <-- Check if value has not been calculated.
count = f(v, i + 1, S, memo)
count += f(v, i + 1, S - v[i], memo)
memo[(i, S)] = count # <-- Memoize calculated result.
return memo[(i, S)] # <-- Return memoized value.
def g(v, S, memo):
subset = []
for i, x in enumerate(v):
# Check if there is still a solution if we include v[i]
if f(v, i + 1, S - x, memo) > 0:
subset.append(x)
S -= x
return subset
v = [19783,21689,21169,11767,23207,12591]
sum = 56967
memo = dict()
if f(v, 0, sum, memo) == 0: print("There are no valid subsets.")
else: print(g(v, sum, memo))
returns [21169, 23207, 12591]
however if change 21169 to 21168 it returns "no valid subsets"
v = [19783,21689,21168,11767,23207,12591]
