動的計画法（１） ナップサック問題
1月 22nd, 2009 admin
あと2問で終わりとなった「アルゴリズムとデータ構造シリーズ」です。今回は第11章「動的計画法」のナップサック問題です。
動的計画法
深さ優先探索や幅優先探索などの分割統治法（トップダウン的問題解決法）では指数的に計算量が増えてしまうような問題というのがあります。（本書では例として「４３ペンスのお釣りを出すときに考えられる小銭の組合せ」という問題があげられていました）そのような問題を解決するひとつの方法としてあるのが動的計画法というもので、
全体をいくつかの小問題に分割して、先に一括して小問題の解をすべて得て、最終的にそれらを組み合わせて問題の解決に役立てる。
だそうです。いつもは自分の言葉で説明するのですが、このアルゴリズムは説明しにくい。理解してないということかもしれません・・・
コード
ナップサック問題というのを解く問題です
RUBY:
-
class Product
-
attr_accessor :size, :value
-
-
def initialize(size,value)
-
@size = size
-
@value = value
-
end
-
end
-
-
products = [
-
Product.new(2,2),
-
Product.new(3,4),
-
Product.new(5,7),
-
Product.new(6,10),
-
Product.new(9,14)
-
]
-
-
NAP_SIZE = 16
-
NAP_SIZE_RANGE = 1..NAP_SIZE
-
nap_value = Array.new.fill(0,0..NAP_SIZE)
-
-
printf("nap size ");
-
NAP_SIZE_RANGE.each do |j|
-
printf(" %2d",j)
-
end
-
puts "\n"
-
-
0..products.size.times do |i|
-
NAP_SIZE_RANGE.each do |j|
-
-
if j - products[i].size>= 0
-
new_value = (nap_value[j - products[i].size] || 0) + products[i].value
-
else
-
new_value = 0
-
end
-
-
nap_value[j] = new_value if new_value> nap_value[j]
-
end
-
-
printf("use product until #%d ", i+1);
-
NAP_SIZE_RANGE.each do |j|
-
printf("%2d ",nap_value[j])
-
end
-
puts "\n"
-
end
まとめ
これを使うべきときに思い出せるかどうか不安。
※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。
