Question

Help in ps8, applying dynamic programming to brute force algorithm.

Answer 1

def dpAdvisorHelper(subjects,maxWork,i,bestSubset,bestSubsetValue,subset,subsetValue,subsetWork,memo):
try: return memo[tuple(subset)]
except KeyError:
# Hit the end of the list.
if i >= len(subjects):
memo[tuple(subset)] = subsetValue
if bestSubset == None or subsetValue > bestSubsetValue:
# Found a new best.
return subset[:], subsetValue
else:
# Keep the current best.
return bestSubset, bestSubsetValue
else:
s = subjects[i]
# Try including subjects[i] in the current working subset.
if subsetWork + s[WORK] <= maxWork:
subset.append(i)
memo[tuple(subset)] = subsetValue
bestSubset, bestSubsetValue = dpAdvisorHelper(subjects,
maxWork, i+1, bestSubset, bestSubsetValue, subset,
subsetValue + s[VALUE], subsetWork + s[WORK],memo)
subset.pop()

bestSubset, bestSubsetValue = dpAdvisorHelper(subjects,
maxWork, i+1, bestSubset, bestSubsetValue, subset,
subsetValue, subsetWork,memo)

return bestSubset, bestSubsetValue

This returns an error that 'int' type isn't iterable. and I think the problematic line is:
if subsetWork + s[WORK] <= maxWork:
subset.append(i)
memo[tuple(subset)] = subsetValue

Because if I remove the memo part it works fine, but I lose the DP advantage I was going for. btw for those who don't remember the problem subset is a list not an int.

Answer 2

post your code to dpaste.com, then post the link here- it will keep all the indentation and i'ts easier to read than on these posts.

are you using windows/idle?? the traceback should tell you the offending line
what data type is subset? if it is a list then this seems to work fine:
memo[tuple(subset)] = 'something'
how far is it recursing before it blows up?
how are you calling it? maybe post dpAdvisor with the Helper (use dpaste.com)
put a print statement in to print your variables to see what they are.

I attached my functions in this post:
http://openstudy.com/updates/4db64530c08f8b0bdc9531c3#/updates/4dabeb7ad6938b0bfe60a74d