﻿

# 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