Added 0/1 Knapsack implementation

Yonaba · Yonaba · commit 8d1edbdc8326 · 2014-01-30T21:26:19.000Z
Both implementations now returns the maximum profit
Added comments
Updated tests
diff --git a/Knapsack/Lua/Yonaba/knapsack.lua b/Knapsack/Lua/Yonaba/knapsack.lua
@@ -15,32 +15,88 @@ end
 --   ...
 -- }
 -- In the returned output, each item will receive a new attribute 'p'
--- referring to how much (percentage) of the item has been added into 
+-- 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)
+-- items   : an array of items  (see note before). This array will be
+-- sorted regarding their benefits in decreasing order.
 -- capacity: the maximum capacity of the knapsack
--- returns : an array of items
+-- returns : 1. an array of items
+--           2. the maximum profit
 local function fractionalKnapsack(items, capacity)
   table.sort(items, function(a, b) return a.b > b.b end)
-  local inKnapsack = {}
+  local inKnapsack, profit = {}, 0
   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)
+    profit = profit + max_item.b
   end
-  return inKnapsack
+  return inKnapsack, profit
+end
+
+
+-- Performs standard 0/1 Knapsack, meaning that an item is either
+-- picked or not. This implementation uses dynamic programming.
+-- items   : an array of items (see note before).
+-- capacity: the maximum capacity of the knapsack
+-- returns : 1. an array of items
+--           2. the maximum profit
+local function integerKnapsack(items, capacity
+	-- Get the count of items
+  local numOfItems = #items
+  
+  -- Auxiliary tables for dynamic search and selected items tracking
+	local V, K = {}, {}
+
+  -- Inits auxiliary tables with 0's. Note that although
+  -- Lua's arrays start at 1, we start looping at 0
+	for i = 0, numOfItems do
+		V[i], K[i] = {}, {}
+		for w = 0, capacity do
+			V[i][w], K[i][w] = 0, 0
+		end
+	end
+
+  -- Dynamic search
+	for i = 1, numOfItems do
+		local item = items[i]
+		for w = 0, capacity do
+			if item.w < w
+        and (item.b + V[i - 1][w - item.w] > V[i - 1][w]) then
+          V[i][w] = item.b + V[i-1][w - item.w]
+          K[i][w] = 1
+			else
+				V[i][w] = V[i - 1][w]
+				K[i][w] = 0
+			end
+		end
+	end
+
+  -- Process auxiliary tables to identify
+  -- selected items and evaluate the profit
+  local inKnapsack, profit = {}, 0
+	for i = numOfItems, 1, -1 do
+    local item = items[i]
+		if K[i][capacity] == 1 then
+			table.insert(inKnapsack, item)
+			capacity = capacity - item.w
+      profit = profit + item.b
+		end
+	end
+
+  return inKnapsack, profit
 end
 
 return {
   fractional = fractionalKnapsack,
+  integer    = integerKnapsack
 }
 
 
diff --git a/Knapsack/Lua/Yonaba/knapsack_test.lua b/Knapsack/Lua/Yonaba/knapsack_test.lua
@@ -29,15 +29,31 @@ run('Testing fractional knapsack', function()
     {name = 'Rice', w = 5, b = 6},
   }
   local capacity = 10
-  local sack = knapsack.fractional(items, capacity)
+  local sack, profit = 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))
+  print(profit)
+  assert(fuzzyEq(profit, 12.67))
 end)
 
+run('Testing integer knapsack', function()
+  local items = {
+    {name = 'Apple', w = 5, b = 10},
+    {name = 'Orange', w = 4, b = 40},
+    {name = 'Salt', w = 6, b = 30},
+    {name = 'Pepper', w = 3, b = 50},
+  }
+  local capacity= 10
+  local sack, profit = knapsack.integer(items, capacity)
+  assert(#sack == 2)
+  local s1, s2 = sack[1], sack[2]
+  assert(s1.name == 'Pepper' and s1.w == 3 and s1.b == 50)
+  assert(s2.name == 'Orange' and s2.w == 4 and s2.b == 40)
+  assert(profit == 90)
+end)
 
 print(('-'):rep(80))
 print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
