2011年07月18日

部分和問題を動的計画法で解く

   このエントリーをはてなブックマークに追加 Clip to Evernote
部分和問題とは、
「与えられた n 個の整数(集合A)と 整数 X があった時に、集合Aから任意の数の整数を選び、
その数の和(部分和)が、X に等しくなるような、部分集合を求める」 というものです。

たとえば、 [3,7,8,12,13,18] の部分和が 27 になる部分集合は、[7,8,12] となります。

このような問題を解くには、バックトラックでも解くことは可能ですが、要素の数が多くなると
組合せの数が増えすぎて、対応できなくなることもあり得ます。
このような時に利用するのが、動的計画法です。

僕のWebサイト「Gushwell's C# Programming Page」に、この部分和問題を解くプログラムコードを掲載しました。

興味のある方はどうぞ。



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52174204