Question

So for ps8 problem 2, what exactly is it asking us to do?
Is it asking us to compare every single value to every other value in the dictionary? Such as:

for i in subjects.keys():
subInfo1 = subjects[i][0]
for k in subjects.keys():
subInfo2 = subjects[k][0]
comparator(subInfo1, subInfo2)

Cause that is a lot of comparisons. Are we trying to prove that this is not the best solution for a problem like this, like the maxVal problem he did in class. I'm just a little confused. Can someone please help me out please.

Any help is much appreciated.

Thanks

Answer 1

you are implementing a greedy algorithm to solve this particular knapsack problem -
the key feature of greedy is that it picks the BEST item (subject) first. Then the Next Best ....

Answer 2

Yes you have to do a lot of comparisons but it runs fast. :) In part 4 of the problem you will be asked to code a DP solution where you are trying to get the list of courses that offer the most value while not exceeding maxWork. After you finish part 4 you can compare the greedy solution using the cmpValue comparator with the DP solution from part 4 and I think you should find that the DP solution is more optimal for a given maxWork.

Answer 3

So then that is the right way of doing it? Thanks

Answer 4

And then once I reach the limit without going over maxWork then I don't have to do anymore comparisons. So if maxWork is 15 and the first 2 values are 9 and 6, I can stop the iterations? Does that make sense?

Answer 5

Right, after the combined course worload reaches maxWork no more comparisons are needed.

Answer 6

Ok, awesome, thanks for all the help