Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

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

0 votos
94 visitas
perguntada Abr 9, 2016 em Ciência da Computação por danielcajueiro (5,726 pontos)  
Compartilhe

1 Resposta

0 votos
respondida Abr 9, 2016 por danielcajueiro (5,726 pontos)  

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
comentou Abr 14, 2016 por PRosa (61 pontos)  
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
comentou Abr 15, 2016 por danielcajueiro (5,726 pontos)  
Obrigado pela dica! Vou checar!
comentou Abr 15, 2016 por danielcajueiro (5,726 pontos)  
Corrigido! Muito obrigado!
...