knapsack


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- 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  (see note before). This array will be
-- sorted regarding their benefits in decreasing order.
-- capacity: the maximum capacity of the knapsack
-- 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, 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, 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
}

-- 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, profit = knapsack.fractional(items, capacity)
  assert(#sack == 3)
  local s1, s2, s3 = sack[1], sack[2], sack[3]
  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 %%')
  :format(total, pass, total-pass, (pass*100/total)))