Question

Struggling a lot with Dynamic Programming

Answer 1

Im on problem 8 and I really don't understand DP that much. From what I understand, its just Brute Force where you keep track of the optimal solution or all the previous solutions, right?

Here is what ive done for PS8:
bestSub = {}
for i in subjects.keys():
if maxWork - subjects[i][WORK] < 0:
return
else:
max(dpAvdvisor(subjects, maxWork-(subjects[i][WORK])[VALUE]), bestSub[VALUE])

Unfortunately, I'm totally lost, even watching the lectures over and over. What am I missing?

Answer 2

Check some other sources. Wikipedia's DP article: https://en.wikipedia.org/wiki/Dynamic_programming

Answer 3

Ok, so i figured out how to find the Value via memoization BUT I don't know how to access the specific subjects.

def dpAdvisor(subjects, maxWork):
ListSub, ListValue, ListWork, memo = [],[],[],{}
for i in subjects.keys():
ListSub.append(i)
ListValue.append(subjects[i][VALUE])
ListWork.append(subjects[i][WORK])
BestValue = dpAdvisorHelp(maxWork, ListSub, ListValue, ListWork, memo, len(ListSub)-1)
print BestValue


def dpAdvisorHelp(maxWork, ListSub, ListValue, ListWork, memo, i):
try: return memo[(i,maxWork)]
except KeyError:
if i==0:
if ListWork[i] <= maxWork:
memo[(i,maxWork)] = ListValue[i]
return ListValue[i]
else:
memo[(i,maxWork)] = 0
return 0
Forget_i = dpAdvisorHelp(maxWork, ListSub, ListValue, ListWork, memo, i-1)
if ListWork[i] > maxWork:
memo[(i,maxWork)] = Forget_i
return Forget_i
else:
Use_i = ListValue[i] + dpAdvisorHelp(maxWork - (ListWork[i]), ListSub, ListValue, ListWork, memo, i-1)
I_Dont_Know = max(Forget_i, Use_i)
memo[(i, maxWork)] = I_Dont_Know
return I_Dont_Know

Can someone please help me figure out how to save the subjects that give me the highest value?

Answer 4

That is exactly the problem I'm having, I thought about a list but you run into problems with aliasing, which is similar to problems with the string. It has gotten tough. Maybe referencing that relevant dictionary key and appending it to that specific value, and appending it. Let me know if you get it.

Answer 5

def dictionaryappend(PreviousValues,classes,counter,available,value,hours):
add=PreviousValues[(classes[counter],available)][1]
stay=PreviousValues[(classes[counter],available)][0]
add=add+", "+str(classes[counter])
PreviousValues[(classes[counter],available)]=[stay,add]
return None
I'm having trouble with other parts, but this may very well do it. A function gets whatever the current string is and adds the current course to it.