Skip to content

Instantly share code, notes, and snippets.

@pachacamac
pachacamac / bin_packer.rb
Last active December 10, 2016 08:39
1d first fit decreasing bin packing algorithm (see https://en.wikipedia.org/wiki/Bin_packing_problem)
def decreasing_first_fit(elements, max_bin_size)
bins = [elements.first.class.new]
elements.sort_by{|e| e.size}.reverse.each do |e|
found_place = false
bins.each_with_index do |bin, i|
if bin.size + e.size <= max_bin_size
bins[i] += e
found_place = true
#puts "found place for #{e} in bin #{i}"
break