動的計画法で部屋の割り当て

「Rubyによる情報科学入門」（久野靖著）にあった動的計画法をやってみた。またしてもコードがRubyらしくない気がしたので、書き換えてみた。

動的計画法は、ある条件を満たす解を見つけるのに、その解だけを求めるのじゃなくて、初期状態から順次計算していくことで大幅に計算量を減らすアプローチの一般的な呼び方らしい。Ruby情報科学本には、編集距離の計算やパターン認識も動的計画法の応用例に挙がっている。

問題は1人部屋5000円、3人部屋1万2000円、7人部屋2万円の旅館があったとき、n人がもっと安く泊まるのに必要な部屋の組み合わせを求めよ、というもの。

=begin
Dynamic programming excercise

[Room charge]
Type A ...  5000yen   accomodates 1 person
Type B ... 12000yen   accomodates 3 persons
Type C ... 20000yen   accomodates 7 persons

Given the number of people(n < 100), what's the cheapest reservation
choice? 
=end

class Room

  attr_reader :price, :rooms

  def initialize(max)
    @price = Array.new(max, 0)
    @rooms = [0]
    @max = max
    make_table
  end

  def make_table
    (1...@max).each do |i|
      @price[i] = @price[i - 1] + 5000
      room = 1
      
      if @price[i] > @price[i - 3] + 12000
        @price[i] = @price[i - 3] + 12000
        room = 3
      end
      
      if @price[i] > @price[i - 7] + 20000
        @price[i] = @price[i - 7] + 20000
        room = 7
      end
      @rooms << room
    end
  end
end

if __FILE__ == $0

  r = Room.new(100)

  while true
    print "How many people? : "
    n = gets.to_i
    print "#{r.price[n]} yen\n"
    while (n > 0) do
      print "#{r.rooms[n]} "
      n = n - r.rooms[n]
    end
    puts
  end

end

ほとんど本にあるものの翻案だけど、やってみるとバグる。配列をインデックスアクセスするのって意味が分かりづらいから、@rooms << roomとしたのだけど、このとき、初期化のところで、

@price = Array.new(max, 0)
@rooms = Array.new(max, 0)

のままにしてしまった。必要な量を確保してpushすると、0,0,0,0,……,1,2,3,4のように最初のほうは0行進になるに決まってるのだけど、実行するまで気づかなかった。

次に、

@price = Array.new(max, 0)
@rooms = []

として失敗した。配列の添字は、1人のところから始めているので、結果がひとつずつずれた。正しくは、

@price = Array.new(max, 0)
@rooms = [0]

とする必要があった。