packer.rb

gistfile1.rb

# Problem:
#
# I have a number of items that need to be shipped.
# Each item is less than one pound.
# Each shipment can contain a maximum of one pound of items.
# How can I efficiently pack the packages?

class BoxContainer
  attr_reader :boxes

  def initialize items
    @boxes = [Box.new]

    items.sort_by(&:weight).reverse.each do |item|
      self << item
    end
  end

  def << item
    @boxes.each do |box|
      if box.can_hold?(item)
        box << item
        return
      end
    end
    box = Box.new
    box << item
    @boxes << box
  end

end

class Box
  MAX_SIZE = 1

  def initialize
    @items = []
  end

  def << item
    @items << item
  end

  def can_hold? item
    weight + item.weight <= MAX_SIZE
  end

  def weight
    @items.map(&:weight).inject(:+) || 0
  end
end

Package = Struct.new(:weight)

require 'test/unit'

class Tests < Test::Unit::TestCase
  def number_of_packages list
    BoxContainer.new(list).boxes.size
  end

  def test_1
    list = [0.9, 0.5, 0.1, 0.5].map { |i| Package.new(i) }
    assert_equal 2, number_of_packages(list)
  end

  def test_2
    list = [Package.new(0.9)]
    assert_equal 1, number_of_packages(list)
  end

  def test_3
    list = [0.9, 0.2].map { |i| Package.new(i) }
    assert_equal 2, number_of_packages(list)
  end

  def test_4
    list = [0.9, 0.5, 0.1, 0.5, 0.1, 0.1, 0.5, 0.7, 0.1, 0.5].map { |i| Package.new(i) }
    assert_equal 4, number_of_packages(list)
  end
end