効率的なアルゴリズム
ある整数を要素に持つ配列の部分配列を考えたときに、その部分配列の要素の合計値が、ある値以下で且つ、最大になるような部分配列を洗い出したい。
http://q.hatena.ne.jp/1386755073
(意訳)
Ruby でやってみた。
def sum(list) a = 0 list.each { |i| a += i } return a end def listup(a, limit_value) ans = [] first = a[0] # 要素がひとつだったら、限界値を超えていなければ、解として採用 if a.size == 1 then if first <= limit_value then ans = [[ first ]] end # 要素が複数 else # 先頭の値が限界値以下なら、それを除いたリストに対して、 # 「限界値−先頭の値」を限界値として、探索 b = [] if first <= limit_value then sub = listup(a[1..a.size-1], limit_value - first) if sub.empty? then b = [[ first ]] else b = sub.collect { |item| [ first ] + item } end end # 先頭の値を除いたリストに対して探索 c = listup(a[1..a.size-1], limit_value) # ふたつをマージ b = b + c # 候補の中から、合計値が一番大きいものを解として採用 v_max = 0 b.each { |item| v = sum(item) if v_max < v then ans = [ item ] v_max = v elsif v_max == v then ans.push item end } end return ans end def test(a, limit) puts "** [#{a.join(',')}] <= #{limit}" listup(a, limit).each_with_index { |d, idx| puts "#{idx + 1} : [#{d.join(',')}]" } puts "-----------" end test([6,10,100,8,4], 111) test([1, 2, 3, 4, 5], 5) test([1, 2, 3, 4, 5], 4) test([41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199], 195)
実行結果。
** [6,10,100,8,4] <= 111 1 : [6,100,4] 2 : [10,100] ----------- ** [1,2,3,4,5] <= 5 1 : [1,4] 2 : [2,3] 3 : [5] ----------- ** [1,2,3,4,5] <= 4 1 : [1,3] 2 : [4] ----------- ** [41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199] <= 195 1 : [41,47,107] 2 : [41,53,101] 3 : [41,71,83] 4 : [43,73,79] 5 : [47,59,89] 6 : [53,59,83]
多分、正しく動いてる。
でも、効率が良いか、っていうとどうだろう。
限界値を超えたら打ち切っているので、全ての組合せを総当たりするよりは、効率が良くなっているとは思うけど。
ideone.com のは こちら。