## knapsack

### Data

#### Tags

combinatorics, optimization

### 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
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, sack, sack
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, sack
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)))
``````