타입 별 구속 조건이있는 Python 배낭

Question

여기 NIT에서 가져온 간단한 배낭 문제는 here에서 가져 왔습니다.

스크립트는 가중치와 값을 최적화하지만 클래스 반복이 없도록 스크립트를 최적화하고 싶습니다. 나는 10의 모자를 가지고 예를 들어 그래서, 그것은 w[0] v[0] c[0] and w[2] v[2] c[2]을 반환하고 NOT 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)