Uma solução bem ineficiente baseada em busca exaustiva é
from itertools import combinations
def generate_all_combinations(n):
myList = range(n)
sizeList=len(myList)
allCombinations=[]
for theSize in range(0,sizeList+1):
for combination in combinations(myList,theSize):
allCombinations.append(combination)
return allCombinations
if __name__ == '__main__':
capacity=32
listWeights=[]
listWeights.append(7)
listWeights.append(9)
listWeights.append(17)
listWeights.append(23)
listWeights.append(25)
listValues=[]
listValues.append(1)
listValues.append(2)
listValues.append(3)
listValues.append(2)
listValues.append(1)
numberItens=len(listWeights)
allCombinations=generate_all_combinations(numberItens)
numberCombinations=len(allCombinations)
maxValue=0
solution=[]
for i in range(numberCombinations):
numberElementsInCombination=len(allCombinations[i])
if(numberElementsInCombination!=0):
weight=0
value=0
for j in range(numberElementsInCombination):
weight=weight+listWeights[allCombinations[i][j]]
value=value+listValues[allCombinations[i][j]]
if(weight<=capacity):
if(value>maxValue):
solution=allCombinations[i]
maxValue=value
print solution