people_jobs = {0:[9,2,7,8],
1:[6,4,3,7],
2:[5,8,1,8],
3:[7,6,9,4]}
import Queue
bestList=[]
class Node:
def __init__(self,level,value,bound,ans):
self.level=level
self.value=value
self.bound=bound
self.ans=ans
def get_Bound(node,people_jobs):
lowerBound = node.value
j = node.level + 1
while j < len(people_jobs[0]):
lowerBound = lowerBound + min(people_jobs[j])
j = j + 1
return lowerBound
def solve_assignment(people_jobs):
numberJobs=len(people_jobs[0])
queue=Queue.PriorityQueue()
root=Node(-1,0,0,[])
queue.put((0,root))
minvalue=10000000000
while not queue.empty():
v=queue.get()[1]
print "Level: ",v.level,"Value: ",v.value, "Bound: ",v.bound,"Value ",v.value,"Ans ",v.ans
if(v.bound<minvalue and v.level<numberJobs-1):
uLevel=v.level+1
for i in range(0,numberJobs):
if i not in v.ans:
uValue=v.value+people_jobs[uLevel][i]
uAssignment=v.ans[:]
uAssignment.append(i)
u=Node(uLevel,uValue,0,uAssignment)
uBound=get_Bound(u,people_jobs)
u=Node(uLevel,uValue,uBound,uAssignment)
if u.level==numberJobs-1 and u.value<minvalue:
minvalue=u.value
global bestList
bestList=u.ans[:]
if u.bound<minvalue:
queue.put((u.bound,u))
print "minValue",minvalue
return minvalue,bestList
solve_assignment(people_jobs)