Question

Working on ps8 and having trouble with problem 4. Anybody have this one solved or able to discuss it?

Answer 1

what are you having trouble with? When I worked on that problem, the memo was the hard part...

Answer 2

I'm having trouble getting the dpAdvisor to work. Did you modify the bruteForceAdvisor to create dpAdvisor or just start from scratch?

Answer 3

Is the memo the dictionary where the previous calls are stored?

Answer 4

yes, that's the memo

Answer 5

I think I redid it from scratch, except for the idea of having a recursive dpAdvisorHelper() that does the work. I made more explicit for me the left - right branching of the recursion just like in the lecture.

This still was by far the hardest assignment for me because I had an evil bug lurking in my code that took me hours to find. I was keeping track of sets of courses in the memo using dictionary objects like in the rest of the problem set code. Then when I took the branch that added the current course to the set of courses being examined, I was modifying the dictionary object that had been returned by the recursive function, which was actually the same object as inside the memo, so I was mutating the left branch objects in my memo when I created the right branch objects.

But at least I probably will remember how to use copy() next time.

Answer 6

This was really hard...
I modified the code used in class for the knap sack problem:
m={}
schedule=[]
listwo=[]
listw=[]
keys=subjects.keys()

vals=subjects.values()
values=[0]*len(vals)

for i in range(len(vals)):
values[i]=vals[i][VALUE]

works=[0]*len(values)

for i in range(len(vals)):
works[i]=vals[i][WORK]

def smart(values,works,i,aW,m):
try:
return m[(i,aW)]
except KeyError:
if i==0:
if works[i]<=aW:
listw=[]
listw=listw+[i]
m[(i,aW)]=[values[i],listw]
return [values[i],listw]
else:
listwo=[]
m[(i,aW)]=[0,listwo]
return [0,listwo]
without_i,listwo=smart(values,works,i-1,aW,m)
if works[i]>aW:
schedule=listwo
m[(i,aW)]=[without_i,schedule]
return [without_i,schedule]
else:
temp=smart(values,works,i-1,aW-works[i],m)
withi=values[i]+temp[0]
listw=[i]+temp[1]
if max(without_i,withi)==withi:
schedule=listw
else:
schedule=listwo
res=[max(without_i,withi),schedule]
m[(i,aW)]=res
return res

def smartAdviser(values,works,i,aW,m):
for i in smart(values,works,i,aW,m)[1]:
print subjects.keys()[i]

Answer 7

jdanayalator, thank you. That code was what I began to attempt, but then gave up when I realized the difficulty. Glad I got to see how it'd be done, and it ran soo much faster than the one I had.

Answer 8

This version is a bit shorter but I think it still works as a replacement for jdanayalator's smart. Please let me know if it has any bugs.

def dpAdvisorHelper(v,w,i,aW,m):
"""
v : list of values
w : list of work costs
i : index '(length of subjects dictionary) - 1'
aW: available Work
m : memo
Returns: A tuple with the max value in index 1
and the list of indexes in index 2.
"""
try: return m[(i, aW)]
except KeyError:
if i == 0:
if v[i] <= aW:
m[(i, aW)] = v[i], [i]
return v[i], [i]
else:
m[(i, aW)] = 0, []
return 0, []

without_i, listWo = dpAdvisorHelper(v,w,i-1,aW,m)
if w[i] > aW:
m[(i, aW)] = without_i, listWo
return without_i, listWo
else:
with_i, listW = dpAdvisorHelper(v,w,i-1,aW-w[i],m)
with_i += v[i]
listW.append(i)

res = max((with_i, listW), (without_i, listWo))
listWo = []
listW = []
m[(i, aW)] = res
return res