knapsack.coffee

#global portviz:false, _:false

#
# * 0-1 knapsack solution, recursive, memoized, approximate.
# *
# * credits:
# *
# * the Go implementation here:
# *   http://rosettacode.org/mw/index.php?title=Knapsack_problem/0-1
# *
# * approximation details here:
# *   http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf
# *
# * details: https://github.com/truher/truher.github.com/wiki/Knapsack
#
_ = require('underscore')

class Memoization
  constructor: ->
    @memory = {}

  key: (i, w) ->
    i + "::" + w

  get: (i, w) ->
    @memory[@key(i, w)]

  put: (i, w, r) ->
    @memory[@key(i, w)] = r

class Knapsack
  constructor: (@items, epsilon = 0.01) ->
    maxValue = _.max(_.pluck(@items, 'value'))
    @scaleK = epsilon * maxValue / @items.length
    @memory = new Memoization()

  subproblem: (i, W) ->
    i = Math.round(i)
    W = Math.round(W)
    if i < 0 or W is 0
      return (
        items: []
        totalWeight: 0
        totalValue: 0
      )
    mm = @memory.get(i, W)
    return mm  unless _.isUndefined(mm)
    item = @items[i]
    return @memory.put(i, W, @subproblem(i - 1, W))  if item.weight > W
    excluded = @subproblem(i - 1, W)
    included = @subproblem(i - 1, W - item.weight)
    if included.totalValue + Math.floor(item.value / @scaleK) > excluded.totalValue
      i1 = included.items.slice()
      i1.push item
      return @memory.put(i, W,
        items: i1
        totalWeight: included.totalWeight + item.weight
        totalValue: included.totalValue + Math.floor(item.value / @scaleK)
      )
    @memory.put i, W, excluded

  one: (maxweight) ->
    scaled = @subproblem(@items.length - 1, maxweight)
    items: scaled.items
    totalWeight: scaled.totalWeight
    totalValue: scaled.totalValue * @scaleK

  ef: (maxweight, step) ->
    for weight in [0...maxweight + 1] by step
      scaled = @subproblem(@items.length - 1, weight)
      items: scaled.items
      totalWeight: scaled.totalWeight
      totalValue: scaled.totalValue * @scaleK

exports.Knapsack = Knapsack

knapsack.test.coffee

#global portviz:false, _:false

#
# * after rosettacode.org/mw/index.php?title=Knapsack_problem/0-1
# *
# * details: https://github.com/truher/truher.github.com/wiki/Knapsack
#
# Run with nodeunit for example

_ = require('underscore')
Knapsack = require('./knapsack').Knapsack

allwants = [
  {
    name: "map"
    weight: 9
    value: 150
  }
  {
    name: "compass"
    weight: 13
    value: 35
  }
  {
    name: "water"
    weight: 153
    value: 200
  }
  {
    name: "sandwich"
    weight: 50
    value: 160
  }
  {
    name: "glucose"
    weight: 15
    value: 60
  }
  {
    name: "tin"
    weight: 68
    value: 45
  }
  {
    name: "banana"
    weight: 27
    value: 60
  }
  {
    name: "apple"
    weight: 39
    value: 40
  }
  {
    name: "cheese"
    weight: 23
    value: 30
  }
  {
    name: "beer"
    weight: 52
    value: 10
  }
  {
    name: "suntan cream"
    weight: 11
    value: 70
  }
  {
    name: "camera"
    weight: 32
    value: 30
  }
  {
    name: "T-shirt"
    weight: 24
    value: 15
  }
  {
    name: "trousers"
    weight: 48
    value: 10
  }
  {
    name: "umbrella"
    weight: 73
    value: 40
  }
  {
    name: "waterproof trousers"
    weight: 42
    value: 70
  }
  {
    name: "waterproof overclothes"
    weight: 43
    value: 75
  }
  {
    name: "note-case"
    weight: 22
    value: 80
  }
  {
    name: "sunglasses"
    weight: 7
    value: 20
  }
  {
    name: "towel"
    weight: 18
    value: 12
  }
  {
    name: "socks"
    weight: 4
    value: 50
  }
  {
    name: "book"
    weight: 30
    value: 10
  }
]

near = (actual, expected, tolerance) ->
  return true  if expected is 0 and actual is 0
  return Math.abs(expected - actual) / actual < tolerance  if expected is 0
  Math.abs(expected - actual) / expected < tolerance

exports.KnapsackTest =

  'one knapsack': (test) ->
    combiner = new Knapsack(allwants)
    oneport = combiner.one(400)
    test.ok near(oneport.totalValue, 1030, 0.01), "correct total value"
    test.ok near(oneport.totalValue, 1030, 0.01), "correct total value"
    test.equal oneport.totalWeight, 396, "correct total weight"
    test.done()

  'frontier': (test) ->
    combiner = new Knapsack(allwants)
    ef = combiner.ef(400, 1)
    test.equal ef.length, 401, "401 because it includes the endpoints"
    ef = combiner.ef(400, 40)
    test.equal ef.length, 11, "11 because it includes the endpoints"
    expectedTotalValue = [0, 330, 445, 590, 685, 755, 810, 860, 902, 960, 1030]
    _.each ef, (element, index) ->
      # 15% error!  bleah!
      test.ok near(element.totalValue, expectedTotalValue[index], 0.15), "actual " + element.totalValue + " expected " + expectedTotalValue[index]

    test.deepEqual _.pluck(ef, "totalWeight"),
      [0, 39, 74, 118, 158, 200, 236, 266, 316, 354, 396]

    test.deepEqual _.map(ef, (x) ->
        x.items.length
      ), [0, 4, 6, 7, 9, 10, 10, 12, 14, 11, 12]
    test.done()