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

Como resolver o problema da mochila usando a técnica conhecida como Branch and Bound?

0 votos
479 visitas
perguntada Mai 11, 2016 em Ciência da Computação por danielcajueiro (5,661 pontos)  
Compartilhe

1 Resposta

0 votos
respondida Mai 11, 2016 por danielcajueiro (5,661 pontos)  

Um implementação convencional em python. A solução é explicitamente encontrada fazendo uma expansão em uma árvore binária e usando uma fila com prioridades para guardar os nós ainda não explorados. Para calcular o bound de cada nó da árvore, usamos a sugestão do livro Introduction to the Design and Analysis of Algorithms - Anany Levitin página 436.

import Queue
bestList=[]
class Node:
    def __init__(self,level,value,weight,bound,content):
        self.level=level # The level within the tree
        self.value=value # The total value
        self.weight=weight # The total weight
        self.bound=bound   # max (optimistic) value one node can take
        self.content=content   # list of items of node

def get_Bound(u,numberItems,capacity,weights,value):
    if u.weight>=capacity:
        return 0
    else:
        upperBound=u.value
        totalWeight=u.weight
        j=u.level+1
        if j<numberItems:
            upperBound=upperBound+(capacity-totalWeight)*value[j]/weights[j]
        return upperBound 

def solve_Knapsack(weights,values,capacity):
    numberItems=len(weights)
    queue=Queue.PriorityQueue()
    root=Node(-1,0,0,0.0,[])   
    queue.put((0,root))

    maxvalue=-1
    bound=0
    while not queue.empty():
        v=queue.get()[1] # Get the next item on the queue
        print "Level: ",v.level,"Content: ",v.content, "Bound: ",v.bound,"Value",v.value,"weight: ",v.weight
        if(v.bound>maxvalue and v.level<numberItems-1):
            uLevel=v.level+1 
            u=Node(uLevel,v.value+values[uLevel],v.weight+weights[uLevel],0,v.content[:])
            u.content.append(uLevel)
            bound=get_Bound(u,numberItems,capacity,weights,values)
            u.bound=bound

            if (u.weight<=capacity and u.value>maxvalue):
                # Is this the best solution?
                maxvalue=u.value
                global bestList 
                bestList=u.content[:]

            if bound>maxvalue:    
                # Should this solution be considered?
                queue.put((-u.bound,u))

            u = Node(uLevel,v.value,v.weight,0.0,v.content)
            bound = get_Bound(u,numberItems,capacity,weights,values)
            u.bound=bound
            if (bound>maxvalue):
                queue.put((-u.bound,u))
        print "maxValue",maxvalue                
    return maxvalue,bestList


if __name__ == '__main__':


    #  Please, sort the items by value/weight
    capacity=10

    weightList=[]
    weightList.append(4)
    weightList.append(7)
    weightList.append(5)
    weightList.append(3)
    #weightList.append(25)

    valueList=[]
    valueList.append(40)
    valueList.append(42)
    valueList.append(25)
    valueList.append(12)
    #valueList.append(1)    

    print solve_Knapsack(weightList,valueList, capacity)
...