Question

Could someone among you guys tell me if what I've done below is what the problem asked?

I've assumed it was a case of Bubble Sort, so I just borrowed and implemented that design on this problem. To work around the dictionary, I've converted the keys to a list.

Thank you in advance.

Problem Set 8: Dynamic Programming
#
# Problem 2: Subject Selection By Greedy Optimization
#
def greedyAdvisor(subjects, maxWork, comparator):
"""
Returns a dictionary mapping subject name to (value, work) which includes
subjects selected by the algorithm, such that the total work of subjects in
t

Answer 1

#I'm assuming this is a Bubble Sort case:
#I'm using a list with the dictionary keys to move around the dictionary.
list_subjects = list(subjects.keys())
swapped = True
while swapped:
swapped = False
for i in range(len(list_subjects) - 1):
a = subjects[list_subjects[i]]
b = subjects[list_subjects[i + 1]]
if comparator(a, b):
temp = list_subjects[i]
list_subjects[i] = list_subjects[i + 1]
list_subjects[i + 1] = temp
swapped = True
#I now pick as many item as maxWork allows:
result = {}
total_work = 0
for i in range(1, len(list_subjects) + 1):
if subjects[list_subjects[-i]][WORK] <= maxWork - total_work:
result[list_subjects[-i]] = subjects[list_subjects[-i]]
total_work += subjects[list_subjects[-i]][WORK]
return (result)

Answer 2

I'm sorry, but I had to split my message over several posts, otherwise this board didn't let me publish the whole message in one post. My apologies.

This may make the code easier to read: http://dpaste.com/hold/602000/

Answer 3

if i remember correctly, the greedy algorithm just goes through and picks the most valuable item first then the next-most valuable ... till there is no room(work) left. sorting by value then running through and picking each successive item till no work is left should work.
.

Answer 4

does your code work? i found it curious that in line 25 you used -range(len(list_subjects) - 1) - i don't think you will get the last item in the list with that.
.

Answer 5

in line 28 it looks like you are passing subject names to the comparator functions - if you have not modified those functions, i don't think they will work with subject names as the arguments.
.

Answer 6

** spoiler below**you should try to get your sort algorithm working to understand the mechanics -
then if you want try the following:
lists have a sort method that takes a comparison function as a method: see note 8 after this table http://docs.python.org/library/stdtypes.html#mutable-sequence-types
and
http://wiki.python.org/moin/HowTo/Sorting

Answer 7

something like this might work for line 25 - 32:
http://dpaste.com/602068/
.

Answer 8

apparently the key version is faster according to the docsthose are pretty cool - just learned that 'cause you asked the question, thnx