効率的なアルゴリズム

ある整数を要素に持つ配列の部分配列を考えたときに、その部分配列の要素の合計値が、ある値以下で且つ、最大になるような部分配列を洗い出したい。
（意訳）

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 のは こちら。