Advertisement
AlexPritchard

Branch and Bound Knapsack

Apr 11th, 2013
1,619
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.71 KB | None | 0 0
  1. import Queue
  2.  
  3. #w is a list of items' weights and p their corresponding profits
  4. #C is the size of the knapsack
  5. def solveKnapsack(w, p, C):
  6.     n = len(w)
  7.     queue = Queue.Queue()
  8.  
  9.     vLevel = -1
  10.     vProfit = 0
  11.     vWeight = 0
  12.  
  13.     queue.put(vLevel)
  14.     queue.put(vProfit)
  15.     queue.put(vWeight)
  16.     maxProfit = 0
  17.     bound = 0
  18.     while (not queue.empty()):
  19.         vLevel = queue.get()
  20.         vProfit = queue.get()
  21.         vWeight = queue.get()
  22.  
  23.         uLevel = vLevel
  24.         if (vLevel == -1):
  25.             uLevel = 0
  26.         elif (vLevel != (n - 1)):
  27.             uLevel = vLevel + 1
  28.         uProfit = vProfit + p[uLevel]
  29.         uWeight = vWeight + w[uLevel]
  30.         bound = getBound(uLevel, uProfit, uWeight, n, C, p, w)
  31.  
  32.         if (uWeight <= C and uProfit > maxProfit):
  33.             maxProfit = uProfit
  34.  
  35.         if (bound > maxProfit):
  36.             queue.put(uLevel)
  37.             queue.put(uProfit)
  38.             queue.put(uWeight)
  39.  
  40.         uProfit = vProfit
  41.         uWeight = vWeight
  42.         bound = getBound(uLevel, uProfit, uWeight, n, C, p, w)
  43.  
  44.         if (bound > maxProfit):
  45.             queue.put(uLevel)
  46.             queue.put(uProfit)
  47.             queue.put(uWeight)
  48.     return maxProfit
  49.  
  50. def getBound(uLevel, uProfit, uWeight, n, C, p, w):
  51.     j = 0
  52.     k = 0
  53.     totalWeight = 0
  54.     result = 0
  55.  
  56.     if (uWeight >= C):
  57.         return 0
  58.     else:
  59.         result = uProfit
  60.         totalWeight = uWeight
  61.         j = uLevel + 1
  62.         while j < n and (totalWeight + w[j]) <= C:
  63.             result += p[j]#e[j][1]
  64.             totalWeight = newWeight
  65.             j += 1
  66.         k = j
  67.         if (k < n):
  68.             result += (C - totalWeight) * p[k]/w[k]
  69.         return result
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement