Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import Queue
- #w is a list of items' weights and p their corresponding profits
- #C is the size of the knapsack
- def solveKnapsack(w, p, C):
- n = len(w)
- queue = Queue.Queue()
- vLevel = -1
- vProfit = 0
- vWeight = 0
- queue.put(vLevel)
- queue.put(vProfit)
- queue.put(vWeight)
- maxProfit = 0
- bound = 0
- while (not queue.empty()):
- vLevel = queue.get()
- vProfit = queue.get()
- vWeight = queue.get()
- uLevel = vLevel
- if (vLevel == -1):
- uLevel = 0
- elif (vLevel != (n - 1)):
- uLevel = vLevel + 1
- uProfit = vProfit + p[uLevel]
- uWeight = vWeight + w[uLevel]
- bound = getBound(uLevel, uProfit, uWeight, n, C, p, w)
- if (uWeight <= C and uProfit > maxProfit):
- maxProfit = uProfit
- if (bound > maxProfit):
- queue.put(uLevel)
- queue.put(uProfit)
- queue.put(uWeight)
- uProfit = vProfit
- uWeight = vWeight
- bound = getBound(uLevel, uProfit, uWeight, n, C, p, w)
- if (bound > maxProfit):
- queue.put(uLevel)
- queue.put(uProfit)
- queue.put(uWeight)
- return maxProfit
- def getBound(uLevel, uProfit, uWeight, n, C, p, w):
- j = 0
- k = 0
- totalWeight = 0
- result = 0
- if (uWeight >= C):
- return 0
- else:
- result = uProfit
- totalWeight = uWeight
- j = uLevel + 1
- while j < n and (totalWeight + w[j]) <= C:
- result += p[j]#e[j][1]
- totalWeight = newWeight
- j += 1
- k = j
- if (k < n):
- result += (C - totalWeight) * p[k]/w[k]
- return result
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement