Question

Como implementar uma solução computacional para o problema da mochila?

Answer 1

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

Comments

Para melhorar a eficiência, a função generate_all_combinations poderia ser modificada, pois estão sendo gerados elementos de um arranjo, sendo que acho que poderia ser de uma combinação.  Por exemplo, os elementos (0,1,4), (0,4,1), (4,0,1) estão sendo gerados na função.

Ao todo, para n=5, são gerados 326 elementos na lista. A função abaixo gera apenas 31:

def generate_all_combinations_v2(n):

    from itertools import combinations
    myList=range(n)    
    allCombinations=[]
    for i in myList:
        combin=combinations(myList,i)   
        for j in combin:
           allCombinations.append(j)
    
    return allCombinations

---

Obrigado pela dica! Vou checar!

---

Corrigido! Muito obrigado!