caixas.rb

class Caixa
  attr_reader :peso, :capacidade

  def initialize(peso, capacidade)
    @peso = peso
    @capacidade = capacidade
  end
end

class Pilha

  attr_reader :caixas

  def initialize(caixas)
    @caixas = caixas.clone
  end

  def empilha(caixa)
    @caixas.push caixa
  end

  def tamanho()
    @caixas.length
  end

  def eh_valida()
    @caixas.each_with_index do |caixa, i|
      if i+1 < @caixas.length
        return false if caixa.capacidade < peso_total(@caixas[i+1..@caixas.length])
      end
    end
    true
  end

  def peso_total(caixas)
    caixas.collect { |c| c.peso }.reduce(:+)
  end

  def copy()
    Pilha.new(@caixas)
  end
end

class Solucao

  attr_accessor :pai, :pilha, :restantes 

  def initialize(pai, pilha, restantes)
    @pai = pai
    @pilha = pilha
    @restantes = restantes
    @filhos = nil
  end

  def gerar_filhos()
    @filhos = []
    @restantes.each do |caixa|
      nova_pilha = @pilha.copy
      nova_pilha.empilha caixa
      @filhos.push Solucao.new(self, nova_pilha, @restantes - [caixa])
    end
  end

  def filhos()
    self.gerar_filhos() if @filhos == nil
    return @filhos
  end

  def melhor_filho()
    melhor_filho = self
    self.filhos().each do |solucao|
      m = solucao.melhor_filho
      if m.pilha.tamanho > melhor_filho.pilha.tamanho and m.pilha.eh_valida
        melhor_filho = m
      end
    end
    return melhor_filho
  end

  def print()
    return pilha.caixas.to_s
  end
end

class Otimizador

  def initialize(caixas)
    @caixas = caixas
  end

  def otimizar()
    return Solucao.new(nil, Pilha.new([]), @caixas).melhor_filho.print
  end
end

puts Otimizador.new([Caixa.new(3,1), Caixa.new(3,2), Caixa.new(3,3)]).otimizar()
puts Otimizador.new([Caixa.new(2,1), Caixa.new(2,1)]).otimizar()
puts Otimizador.new([Caixa.new(1,1), Caixa.new(1,1)]).otimizar()
puts Otimizador.new([Caixa.new(2,10), Caixa.new(9,9), Caixa.new(2,2)]).otimizar()