https://twitter.com/gongoZ/status/391065716834586624 と問い掛けて「アイテムを大きい順にソートしてもっとも少ないビンに順々に割り当てていく」という案をいただいたので書いてみた

gistfile1.rb

items = {
  'hoge'   => 1,
  'fuga'   => 2,
  'hago'   => 3,
  'foo'    => 1,
  'bar'    => 8,
  'baz'    => 1,
  'piyo'   => 3,
  'gongo'  => 4,
  'dududu' => 2
}

sorted_items = items.sort { |a, b| b[1] <=> a[1] }

boxes = 3.times.map do
  { name: [], weight: 0 }
end

sorted_items.each do |name, weight|
  min_box = boxes.min { |v1, v2| v1[:weight] <=> v2[:weight] }
  min_box[:name] << name
  min_box[:weight] += weight
end

boxes.each.with_index(1) do |box, index|
  puts "box#{index}"
  puts "\tnames:  #{box[:name].join(',')}"
  puts "\tweight: #{box[:weight]}"
end

# Output:
#
#   box1
#       names:  bar,hoge
#       weight: 9
#   box2
#       names:  gongo,fuga,dududu
#       weight: 8
#   box3
#       names:  hago,piyo,baz,foo
#       weight: 8