所以我必须解决课堂上的背包问题。到目前为止,我已经想出了以下内容。我的比较器是确定两个主题中哪一个是更好选择的函数(通过查看相应的 (value,work) 元组)。
我决定迭代工作少于 maxWork 的可能主题,为了找到在任何给定轮次中哪个主题是最佳选择,我将我最近的主题与我们尚未使用的所有其他主题进行了比较。
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
the dictionary is not greater than maxWork. The subjects are chosen using
a greedy algorithm. The subjects dictionary should not be mutated.
subjects: dictionary mapping subject name to (value, work)
maxWork: int >= 0
comparator: function taking two tuples and returning a bool
returns: dictionary mapping subject name to (value, work)
"""
optimal = {}
while maxWork > 0:
new_subjects = dict((k,v) for k,v in subjects.items() if v[1] < maxWork)
key_list = new_subjects.keys()
for name in new_subjects:
#create a truncated dictionary
new_subjects = dict((name, new_subjects.get(name)) for name in key_list)
key_list.remove(name)
#compare over the entire dictionary
if reduce(comparator,new_subjects.values())==True:
#insert this name into the optimal dictionary
optimal[name] = new_subjects[name]
#update maxWork
maxWork = maxWork - subjects[name][1]
#and restart the while loop with maxWork updated
break
return optimal
问题是我不知道为什么这是错误的。我遇到了错误,我不知道我的代码哪里出错了(即使在输入打印语句之后)。帮助将不胜感激,谢谢!