【Ruby】【アルゴリズム】ナップザック問題を解く。
ナップザック問題とは
幾つかの品物があり、この品物にはそれぞれ重量(cost)・価値(point)の2つのパラメータが与えられています。ある一定の重さまで品物を運べるとしたときに、価値の合計の最大値は幾つになるでしょう?
(注)
より綺麗なコードはこちらにあります
(10月10日追記)
学んだこと
・Hashの使い方
ポイント
(1):ここの不等式を[<=]にすることで、最小の個数での最大値となる
作ったコード
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時間半かかった。。ぐう。。
【Ruby】【アルゴリズム】重複組み合わせ。シンプル!
問題
0から9までの数字を重複を許して4つ選ぶ時、
答えはいくつありますか?
若干眠くて口調が変だよ。
(例)
0011 と 1001 と 0101 は同じ
1112 と 1122 は違う
答え(全列挙型Ver)
最初に思いついたのは、0~9999を全部並べて、一個ずつ確認する方法。
既に存在する組み合わせはスキップする。
result = [] i = 0 while i < 10000 candidate = i.to_s.split("") (4 - candidate.length).times do candidate << "0" end candidate.sort! acceptable = true result.each do |data| if data == candidate #並び替えた後 既存と同じ組み合わせになる物は無視 acceptable = false break end end result << candidate if acceptable i += 1 end p result.length
答え(シンプルVer!)
どうやって解いたらもっとスマートかな??と探していたら
for文で事足りますよね、という記事を発見。
確かに!
result =[] i = 0 while i < 10 j = i while j < 10 k = j while k < 10 m = k while m < 10 result << "#{i},#{j},#{k},#{m}" m += 1 end k += 1 end j += 1 end i += 1 end p result.length
早い!
すごい!