Added Knapsack in Lua

Yonaba · Yonaba · commit df435a52284e · 2014-01-29T21:36:18.000Z
diff --git a/Knapsack/Lua/Yonaba/knapsack.lua b/Knapsack/Lua/Yonaba/knapsack.lua
@@ -0,0 +1,46 @@
+-- Knapsack problem algorithm implementation
+-- See: http://en.wikipedia.org/wiki/Knapsack_problem
+
+-- Pops value at the head of an array
+local function pop(s)
+  local head = s[1]
+  table.remove(s, 1)
+  return head
+end
+
+-- Note: the items to be passed should be represented this way
+-- items = {
+--   {name = 'item_name', w = <item_weight>, b = <benefit>},
+--   {name = 'item_name', w = <item_weight>, b = <benefit>},
+--   ...
+-- }
+-- In the returned output, each item will receive a new attribute 'p'
+-- referring to how much (percentage) of the item has been added into 
+-- the knapsack.
+
+-- Performs fractional Knapsack. Fractional here means we can
+-- select a portion of a item. With that respect, this implementation
+-- is greedy.
+-- items   : an array of items (this array will be sorted regarding
+--           their benefits in decreasing order)
+-- capacity: the maximum capacity of the knapsack
+-- returns : an array of items
+local function fractionalKnapsack(items, capacity)
+  table.sort(items, function(a, b) return a.b > b.b end)
+  local inKnapsack = {}
+  while capacity > 0 do
+    local max_item = pop(items)
+    max_item.p = max_item.w > capacity and capacity/max_item.w or 1
+    max_item.b = max_item.p * max_item.b
+    max_item.w = max_item.p * max_item.w
+    capacity = capacity - max_item.w
+    table.insert(inKnapsack, max_item)
+  end
+  return inKnapsack
+end
+
+return {
+  fractional = fractionalKnapsack,
+}
+
+
diff --git a/Knapsack/Lua/Yonaba/knapsack_test.lua b/Knapsack/Lua/Yonaba/knapsack_test.lua
@@ -0,0 +1,44 @@
+-- Tests for knapsack.lua
+local knapsack = require 'knapsack'
+
+local total, pass = 0, 0
+
+local function dec(str, len)
+  return #str < len
+     and str .. (('.'):rep(len-#str))
+      or str:sub(1,len)
+end
+
+local function run(message, f)
+  total = total + 1
+  local ok, err = pcall(f)
+  if ok then pass = pass + 1 end
+  local status = ok and 'PASSED' or 'FAILED'
+  print(('%02d. %68s: %s'):format(total, dec(message,68), status))
+end
+
+-- Fuzzy equality test
+local function fuzzyEq(a,b) return math.abs(a-b) < 1e-2 end
+
+run('Testing fractional knapsack', function()
+  local items = {
+    {name = 'Apple', w = 3, b = 5},
+    {name = 'Orange', w = 4, b = 5},
+    {name = 'Salt', w = 2, b = 3},
+    {name = 'Pepper', w = 1, b = 2},
+    {name = 'Rice', w = 5, b = 6},
+  }
+  local capacity = 10
+  local sack = knapsack.fractional(items, capacity)
+  assert(#sack == 3)
+  local s1, s2, s3 = sack[1], sack[2], sack[3]
+  print('s3', s3.w-1)
+  assert(s1.name == 'Rice' and s1.p == 1 and s1.w == 5 and s1.b == 6)
+  assert(s2.name == 'Orange' and s2.p == 1 and s2.w == 4 and s2.b == 5)
+  assert(s3.name == 'Apple' and fuzzyEq(s3.p,0.33)  and s3.w == 1 and fuzzyEq(s3.b,1.67))
+end)
+
+
+print(('-'):rep(80))
+print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
+  :format(total, pass, total-pass, (pass*100/total)))
