Dividing an array of objects into groups with a balanced aggregate

Question

I am creating a class that takes an array of elements and splits them into an arbitrary number of buckets so that the sum of the sizes of the elements in each bucket is balanced.

I use a naive approach when I just add the next item to the bucket with the lowest overall size until the number of items runs out. This works great for most scenarios, but sometimes fails due to a lack of "planning." I illustrated this with the following example.

---

the code:

Class SplitCollection:

# 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 the scenario when 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'm looking for:

• an alternative approach to solving the same problem or
• a way to increase my existing approach for handling all scripts.

Answer 1

, .

, NP Complete. , ( ) .

, .

, , .