Splitting an array of objects into groups with a balanced aggregate

Question

I am creating a class that takes an array of items and splits them up into an arbitrary number of buckets in a way such that the sum of the items' sizes in each bucket is balanced.

I am using a naïve approach, where I simply put the next item in the bucket with the lowest total size until I run out of items. This works great for most scenarios, but sometimes fails, due to the lack of "planning". I've illustrated this with an example below.

---

Code:

SplitCollection class:

# split_collection.rb
class SplitCollection
  attr_reader :buckets

  def initialize(collection, buckets = 2)
    @collection = collection
    @buckets = Array.new(buckets) { Bucket.new }
    split
  end

private

  def split
    @collection.each do |item|
      @buckets.min { |x, y| x.total <=> y.total } << item
    end
  end
end

Bucket class:

class Bucket
  def initialize
    @items = []
  end

  def total
    @items.reduce(0) { |sum, item| sum + item.size }
  end

  def <<(item)
    @items << item
  end
end

Item class:

class Item
  attr_reader :size

  def initialize(size)
    @size = size
  end
end

---

Here is some code that demonstrates a scenario where the approach fails:

sizes = [2, 4, 2, 2, 4, 2]
#=> [2, 4, 2, 2, 4, 2]

collection = sizes.map { |size| Item.new(size) }
#=> [#<Item:0x007fcdc301fe80 @size=2>, #<Item:0x007fcdc301fe58 @size=4>, #<Item:0x007fcdc301fe30 @size=2>, #<Item:0x007fcdc301fe08 @size=2>, #<Item:0x007fcdc301fde0 @size=4>, #<Item:0x007fcdc301fdb8 @size=2>]

SplitCollection.new(collection).buckets.map(&:total)
#=> [8, 8] (Works!)

SplitCollection.new(collection, 3).buckets.map(&:total)
#=> [6, 4, 6] (Works!)

SplitCollection.new(collection, 4).buckets.map(&:total)
#=> [6, 4, 4, 2] (Doesn't work! Should be [4, 4, 4, 4].)

---

I am looking for either:

1. an alternative approach to solving the same problem, or
2. a way to augment my existing approach to handle all scenarios.

Answer 1

Unfortunately, there is no known efficient way to solve this problem optimally.

This is a variant of the Bin Packing Problem, which is Strongly NP Complete. This means there is no known efficient (polynomial or pseudo polynomial) solution to the problem.

If you really do need optimal solution, you are going to need some exponential algorithm.

Luckily, this is a well studied problem, so there is plenty of literature available about different cases of it.