knapsack.coffee

# Given a list V of item values, and W of item weights, where item i
# has value V[i] and weight W[i], find the optimal selection of i to
# sure fill the knapsack of capcity k with fractions of items.
#
# The values are required to be sorted by descending order of value
# per pound, in order to enable a greedy choice.
#
# The sort incurs a cost of O(n log(n)), assuming efficient merge
# sort.
#
# The below function then costs O(n), for it's iteration through the
# items. Assuming that most items have a weight greater than 1, then
# this is vastly reduced.
fractionalKnapsack = (V, W, k) ->
  i = value = load = 0
  while (load < k) and (i < V.length)
    f = Math.min ((k - load) / W[i]), 1
    load  += f*W[i]
    value += f*V[i]
    ++i
  load: load, value: value


knapsack = fractionalKnapsack [60, 100, 120], [10, 20, 30], 50
console.log knapsack