bin_packing.rb

# A greedy algorithm for bin packing

class Array
  def rest
    self[1..-1]
  end
end

def optimize_pack inventory, order
  loop do
    r = pack(inventory, order)

    return r if r
    order += 1
  end
end

def pack inventory, order
  case
  when inventory.empty?
    nil
  when order < inventory[0]
    pack(inventory.rest, order)
  when order == inventory.first
    [inventory.first]
  else
    x = pack(inventory.rest, order)
    y = pack(inventory.rest, order - inventory.first)

    choices = []
    choices << x if x
    choices << [inventory.first] + y if y

    choices.min_by { |a| a.length }
  end
end


puts nil == pack([], 10)
puts [10] == pack([10, 5], 10)
puts [10, 1] == pack([10, 1], 11)
puts [10, 5] == pack([10, 5, 1], 15)
puts pack([10, 5, 1], 14)
puts [10, 5] == optimize_pack([10, 5, 1], 14)