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

0 votos
836 visitas

## 1 Resposta

0 votos
respondida Mai 11, 2016 por (5,581 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)