CCCoder

Lab 10

Nov 23rd, 2020
514
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. -- "Global" variables
  2. local W = 10
  3. local p = {21, 30, 20, 18}
  4. local w = {3, 5, 4, 6}
  5. local n = #p
  6.  
  7. local class = require "clasp"
  8.  
  9. local Node = class {
  10.     isNode = true,
  11.    
  12.     init = function(self, level, weight, profit)
  13.         self.level = level or 0
  14.         self.weight = weight or 0
  15.         self.profit = profit or 0
  16.         self.bound = bound(self)
  17.     end,
  18. }
  19.  
  20. local PriorityQueue = class {
  21.     init = function(self)
  22.         self.items = {}
  23.     end,
  24.     push = function(self, node)
  25.         if not node.isNode then return end
  26.  
  27.         table.insert(self.items, node)
  28.  
  29.         -- Sorts ascending
  30.         table.sort(self.items, function(a, b)
  31.             return a.weight < b.weight
  32.         end)
  33.  
  34.     end,
  35.     pop = function(self)
  36.         local node = self.items[#self.items]
  37.         table.remove(self.items, #self.items)
  38.         return node
  39.     end,
  40.  
  41.     isEmpty = function(self)
  42.         return #self.items == 0
  43.     end,
  44. }
  45.  
  46. function bound(node)
  47.     if node.weight >= W then return 0 end
  48.    
  49.     local result = node.profit
  50.     local j = node.level + 1
  51.     local totalWeight = node.weight
  52.    
  53.     while j <= n and totalWeight + w[j] <= W do
  54.         totalWeight = totalWeight + w[j]
  55.         result = result + p[j]
  56.         j = j + 1
  57.     end
  58.  
  59.     local k = j
  60.     if k <= n then
  61.         result = result + (W - totalWeight) * (p[k]/w[k])
  62.     end
  63.  
  64.     return result
  65. end
  66.  
  67. function knapsack3()
  68.  
  69.     local PQ = PriorityQueue()
  70.     local v = Node()
  71.     print(v.bound)
  72.     local maxProfit = 0
  73.  
  74.     PQ:push(v)
  75.  
  76.     while not PQ:isEmpty() do
  77.         local v = PQ:pop()
  78.         if v.bound > maxProfit then
  79.  
  80.             local level = v.level + 1
  81.             local weight = v.weight + w[level]
  82.             local profit = v.profit + p[level]
  83.  
  84.             if weight <= W and profit > maxProfit then
  85.                 maxProfit = profit
  86.             end
  87.  
  88.             local newNode = Node(level, weight, profit)
  89.             if newNode.bound > maxProfit then
  90.                 PQ:push(newNode)
  91.             end
  92.  
  93.             local newerNode = Node(level, v.weight, v.profit)
  94.             if newerNode.bound > maxProfit then
  95.                 PQ:push(newerNode)
  96.             end
  97.         end
  98.  
  99.     end
  100.  
  101.     return maxProfit
  102. end
  103.  
  104. local maxProfit = knapsack3()
  105. print(maxProfit)
RAW Paste Data