按类型划分的带约束的蟒蛇背包

Question

这是我从麻省理工学院公开课程中学到的一个简单的背包问题。

该脚本针对权重和值进行了优化，但我希望它进行优化，以便没有类重复。 因此，例如，如果我的上限为 10，它将返回w[0] v[0] c[0] and w[2] v[2] c[2]而不是w[0] v[0] c[0] and w[1] v[1] c[1] and w[2] v[2] c[2]

weight= [5,3,2]
value = [9,7,8]
the_class = ["A","C","C"]
cap = 5
'''
w = the weight of item
v = the value of item
i = index of the item
aW = availible weight left (cap - w[i])
c = class of item
'''
def maxVal(w, v, i, aW,c): 
    if i == 0: 
        if w[i] <= aW: 
            return v[i] 
        else: 
            return 0 
    without_i = maxVal(w, v, i-1, aW, c) 
    if w[i] > aW: 
        return without_i 
    else: 
        with_i = v[i] + maxVal(w, v, i-1, aW - w[i], c) 
    return max(with_i, without_i)
res = maxVal(weight,value, len(value)-1, cap, the_class)
print "The result: ",res

Answer 1

首先从列表中删除不需要的项目。

import itertools as it
from operator import itemgetter
weight= [5,3,2]
value = [9,7,8]
the_class = ["A","C","C"]
cap = 5
# define functions to sort with
classitem = itemgetter(0)
valueitem = itemgetter(1)
weightitem = itemgetter(2)
# combine the list elements to keep them together
classes = zip(the_class, value, weight)
classes.sort(key = classitem)
# use itertools.groupby() to aggregate the classes
for k, g in it.groupby(classes, classitem):
    things = list(g)
    print k, len(things)
    # remove the least valuable duplicates from the class list
    if len(things) > 1:
        things.sort(key = valueitem)
        for thing in things[:-1]:
            classes.remove(thing)
# reconstruct the original lists, sans unwanted duplicates
the_class = map(classitem, classes)
value = map(valueitem, classes)
weight = map(weightitem, classes)