timeslots.rb

# показываем передачи с такими интервалами
SHOW_WAITS = [5, 8, 10]
# при прочих равных, набираем с большим весом
SHOW_WEIGHTS = [10, 20, 30]
K = SHOW_WAITS.length

N = 240 # общая длина замещаемого интервала
M = 40 # столько вариантов оставляем

Variant = Struct.new(:shown_total, :waits, :shown) do
  def show_next(time_slot, show_id)
    wait_time = SHOW_WAITS[show_id]
    new_shown_total = shown_total.dup
    new_shown_total[show_id] += 1
    adjusted_waits = waits.dup
    adjusted_waits[show_id] += wait_time
    new_shown = shown.dup
    new_shown << [time_slot, show_id]

    (0..wait_time).map do |i|
      new_waits = adjusted_waits.map {|j| j - i > 0 ? j - i : 0 }
      Variant.new(new_shown_total, new_waits, new_shown)
    end
  end

  def can_show?(show_id)
    waits[show_id] <= 0
  end

  def total_weight
    shown_total.map.with_index {|n, j| n * SHOW_WEIGHTS[j] }
  end
end

results = Hash.new { |h,k| h[k] = [] }
results[0] = [Variant.new(Array.new(K, 0), Array.new(K, 0), [])]


(0..N).each do |i|
  results[i].sort_by(&:total_weight).reverse.take(M).each do |variant|
    (0...K).each do |j|
      if variant.can_show?(j)
        variant.show_next(i, j).each_with_index do |new_variant, offset|
          results[i + offset] << new_variant
        end
      end
    end
  end
end
p results[N].sort_by(&:total_weight).reverse.take(5)