【Ruby】【アルゴリズム】ナップザック問題を解く。

ナップザック問題とは

幾つかの品物があり、この品物にはそれぞれ重量(cost)・価値(point)の2つのパラメータが与えられています。ある一定の重さまで品物を運べるとしたときに、価値の合計の最大値は幾つになるでしょう？

（注）
より綺麗なコードはこちらにあります
（10月10日追記）

学んだこと

・Hashの使い方

ポイント

（１）：ここの不等式を[<=]にすることで、最小の個数での最大値となる

作ったコード

class Item
  attr_accessor :cost, :point
  def initialize cost, point
    @cost = cost
    @point = point
  end
end

class Knapsack
  attr_accessor :size,:items, :history
  def initialize size, items
    @size = size
    @items = items
    @history = {}
    (size+1).times{ |i| @history[i] ={} }
  end
  def calc(arr)
    return 0 if arr.length == 0
    point = 0
    arr.each do |key, val|
      point += @items[key].point * val
    end
    point
  end
  def make_max_point
    @items.each do |name, item|
      j = item.cost
      while j <= self.size
        #itemを入れてみた結果のほうが大きければ そちらに鞍替え
        if calc(@history[j]) <= 
             calc(@history[j-item.cost]) + item.point #ポイント(1)
          @history[j] = Marshal.load(Marshal.dump(@history[j-item.cost])) 
          @history[j][name] ||= 0
          @history[j][name] += 1
        end
        j += 1
      end
    end
    self
  end
end

items = {
a: Item.new(3, 2),
b: Item.new(4, 4),
c: Item.new(5, 7),
d: Item.new(6, 10),
e: Item.new(9, 14),
}

nap = Knapsack.new(20, items)
result = nap.make_max_point

#napオブジェクトをダンプ
p result

#求める答え
p result.history[20]

　
■実行結果

#<Knapsack:0x2d45c30 @size=20, @items={:a=>#<Item:0x2d45cc0 @cost=3, @point=2>, :b=>#<Item:0x2d45ca8 @cost=4, @point=4>, :c=>#<Item:0x2d45c90 @cost=5, @point=7>, :d=>#<Item:0x2d45c78 @cost=6, @point=10>, :e=>#<Item:0x2d45c60 @cost=9, @point=14>}, @history={0=>{}, 1=>{}, 2=>{}, 3=>{:a=>1}, 4=>{:b=>1}, 5=>{:c=>1}, 6=>{:d=>1}, 7=>{:d=>1}, 8=>{:d=>1}, 9=>{:e=>1}, 10=>{:e=>1}, 11=>{:c=>1, :d=>1}, 12=>{:d=>2}, 13=>{:d=>2}, 14=>{:c=>1, :e=>1}, 15=>{:d=>1, :e=>1}, 16=>{:d=>1, :e=>1}, 17=>{:c=>1, :d=>2}, 18=>{:d=>3}, 19=>{:d=>3}, 20=>{:c=>1, :d=>1, :e=>1}}>
{:c=>1, :d=>1, :e=>1}

3時間半かかった。。ぐう。。