[Python] Issues with memoization and retrieving solutions in a TargetSum problem - What am I...

INTRODUCTION:

The TargetSum problem I am trying to solve is a dynamic programming problem where I am given a list of natural numbers (S) and a target number (tgt). The program is to use the numbers in the list to sum up to the target number, or get as close as possible.

The program should ultimately return a list of numbers used in the original list to get as close to the tgt. There are overall two halves to my code, the first function being targetSum, and the second getBestTargetSum.

targetSum solves sub-problems recursively, based off of the continuously updated tgt, which is the difference between the original target and the sum of the numbers considered to reach the original target.

getBestTargetSum is supposed to memoize (table T) as it calls targetSum, as well as record the solutions into table D. This, I think, is where my issues lie.

ISSUES:

First off, I think my solutions table D is not properly recording, as it does not include all the indices that I expect it to, such as (0,0). In a different version of this code, I had negative values appear in D, which probably indicates that perhaps indices such as (0,0) were lost to the void due to me trying to get rid of negative values from the table...

Second of all, the result of this codes returns exactly the opposite of what it is supposed to do. When given a list of numbers i.e. {1, 2, 3, 4, 5, 10} and a tgt = 15, instead of choosing {5, 10} for a difference of 0, it selects and returns {1, 2, 5} instead.

Here's my code, forgive me for the mess. I am but a noob. NOTE: key is supposed to determine the starting point of table D. I honestly had so much trouble getting this in totality to work that I don't what it should be, much less whether it should exist. Thank you for the help.


def targetSum(S, i, tgt):
k = len(S)

if tgt < 0:
return float('inf')

if i == k and tgt >= 0:
return tgt

else:
return min(targetSum(S, i+1, tgt-S), targetSum(S, i+1, tgt))


def getBestTargetSum(S, tgt):

k = len(S)
D = {} # Solutions table
T = {} # Memo table

# Case 1: At the end
for j in range(tgt+1):
T[(k,j)] = j
#D[(k,j)] = k,j

for i in range(k-1, -1, -1):
for j in range(tgt+1):
# Case 2: Skip
if j < 0:
T[(i,j)] = float('inf')
D[(i,j)] = i+1,j

# Case 3: Choice
else:
include = targetSum(S, i+1, tgt-S)
exclude = targetSum(S, i+1, tgt)

if include <= exclude:
T[(i,j)] = include
if j - S >= 0:
D[(i,j)] = (i+1, j - S)

else:
T[(i,j)] = exclude
D[(i,j)] = (i+1, j)

# Retrieving solution from D
res = []

key = 0,15

while key in D:

value = D[key]

if value[1] != key[1]:
i = key[0]
res.append(S)

key = value
print(i,j,':',res)

return res

Continue reading...