python - 型による制約付きの Python ナップサック

Question

これは、ここから取った MIT オープン コースから取った簡単なナップザックの問題です。

スクリプトは重みと値を最適化しますが、クラスが繰り返されないように最適化したいと思います。たとえば、上限が 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