動的計画法

• ナップザック問題
• バックトラック法による数列分割問題
• 動的計画法による数列分割問題

ナップザック問題

class Product
  attr_reader :size, :value
  def initialize( size, value )
    @size = size
    @value = value
  end
end

class Nap
  def initialize( size )
    @napValue = Array.new( size, 0 )  # ナップザックの価値
  end

  def main( products )
    # 扱う品物を1つずつ増やしていく
    i = 0
    while i < products.length
      # ナップザックの大きさが j のものに対して
      # 品物 i 番を入れてみる
      j = products[i].size
      while j < @napValue.length
        # 品物 i 番を入れてみた場合、新しい価値はどうなるか
        newValue = @napValue[j - products[i].size] + products[i].value
        if newValue > @napValue[j]
          @napValue[j] = newValue
        end
        j += 1
      end
      printf "品物#{i + 1}まで使う : "
      j = 1
      while j < @napValue.length + 1
        num = @napValue[j].to_s + " "
        if num.size == 2
          num = " " + num
        end
        printf num
        j += 1
      end
      printf "¥n"
      i += 1
    end
  end
end


products = [
  Product.new( 2, 2 ), Product.new( 3, 4 ),
  Product.new( 5, 7 ), Product.new( 6, 10 ),
  Product.new( 9, 14 )
]

nap = Nap.new( 16 )
nap.main( products )

バックトラック法による数列分割問題

【注】
　バックトラック法によるスクリプト、どうも結果がおかしいようです。ごめんなさい。

class SeparatorBackTruck
  def initialize
    @value = [15, 3, 7, 6, 10, 4, 13, 2, 3, 6]
    @separator = 3
    
    @sepPos = Array.new( @separator, 0 )
    # 最適な分割とその中のグループの最大和
    @bestSepPos = Array.new( @separator, 0 )
    @bestSepMaxValue = 10000
  end

  def separate( pos, num )
    # 新しい分割場所を設定
    @sepPos[num += 1] = pos

    # 分割が全て決まったら
    if num == @separator
      max = 0
      0.upto( @separator ) do |i|
        start = ( i == 0 ) ? 0 : @sepPos[i - 1]
        last = ( i == @separator ) ? @value.length : @sepPos[i]

        k = 0
        start.upto( last - 1) do |j|
          k += @value[j]
        end
        if k > max
          max = k
        end
      end

      # 最大のグループ和が保存されている和より小さければ
      if max < @bestSepMaxValue
        @bestSepMaxValue = max
        @separator.times do |i|
          @bestSepPos[i] = @sepPos[i]
        end
      end
      return
    end

    # 次の分割場所を設定する
    (pos + 1).upto( @value.length - @separator + num ) do |i|
      separate( i, num )
    end
  end

  def main
    # 最初の分割場所を設定して再帰を呼び出す
    (@value.length - @separator).times do |i|
      separate( i, 0 )
    end

    # 保存された分割場所を表示する
    0.upto( @separator ) do |i|
      start = ( i == 0 ) ? @value.length : @bestSepPos[i - 1]
      last = ( i == @separator ) ? @value.length : @bestSepPos[i]
      start.upto( last - 1) do |j|
        printf "#{@value[j]} "
      end
      if last != @value.length
        printf "| "
      end
    end
  end
end

sep = SeparatorBackTruck.new
sep.main

動的計画法による数列分割問題

class SeparatorActivePlan
  class Cell
    attr_accessor :sol, :num
    def initialize
      @sol = nil
      @num = nil
    end
  end

  def initialize
    @array = [15, 3, 7, 6, 10, 4, 13, 2, 3, 6]
    @separator = 3
  end

  def main
    solutions = Array.new(@array.length)
    solutions.each_index do |i|
      solutions[i] = Array.new( @separator + 1 )
    end

    # 配列の後ろの方から順に埋めていく
    i = @array.length - 1
    while i >= 0
      0.upto( @separator + 1 ) do |j|
        solutions[i][j] = Cell.new
        solutions[i][j].num = 0
        solutions[i][j].sol = 0
        sum = 0
        i.upto( @array.length - 1) do |s|
          sum += @array[s]

          if j == 0 ||
            i == @array.length - 1 ||
            solutions[i][j].num == 0 ||
             (s != @array.length - 1 &&
                solutions[i][j].sol > [sum, solutions[s + 1][j - 1].sol].max )
            if j == 0 || i == @array.length - 1
              solutions[i][j].sol = sum
            else
              solutions[i][j].sol = [sum, solutions[s + 1][j - 1].sol].max
            end
            solutions[i][j].num = s - i + 1
          end
        end
      end
      i -= 1
    end

    # デバッグ用にテーブルを表示
    0.upto( @separator ) do |j|
      @array.length.times do |i|
        printf "#{solutions[i][j].num},#{solutions[i][j].sol} "
      end
      puts
    end

    # 結果表示
    printf "MAX : #{solutions[0][@separator].sol}¥n"
    printf "Sepalate:"
    i = 0
    j = @separator
    while j >= 0 && i != @array.length
      printf "[#{solutions[i][j].num}]"
      i += solutions[i][j].num
      j -= 1
    end
  end
end

sep = SeparatorActivePlan.new
sep.main