Pythonと再帰で解く部分和問題

目的

　こういうことをしようと思った目的は、競技プログラミングにおいてほとんどC++が使われている気がするため、Pythonで書こうとしても資料があまり見つかりません。そこで、簡単な問題くらいは自分で実装するかと思いました。

部分和問題とは

　数字がいくつか与えられていて、その数字をいくつか選んで目的の数を作る問題です。例えば、数字に[1, 2, 3, 4]が与えられているとき、7を作りたい場合は[1, 2, 4]を選ぶか、[3, 4]を選ぶ場合があり、これを求めるということです。

解き方

　多くの場合この部分和問題は、動的計画法で解いている人が多いため今回は再帰を利用した深さ優先探索を使いました。というのは嘘です。Pythonでの実装がよくわかりませんでした。とりあえず、ソースコードは以下に示します。これは、数の個数が増えると計算量がすさまじい速度で上がっていくため、大きいサイズでは使うことができません(正確には時間が膨大になる)。また、Pythonの再帰を使う上で、デフォルトの深さの限界が1000のためそれ以上の深さは他に設定を変える必要がある。

　ソースコードの上でのnは数の個数、aは各数字、kは調べたい数字を表しています。また、bはどの数字を使っているかを示すもので、[1, 3, 7, 6]の数字の中で1と6を使ったとき[1, 0, 0, 1]と表すようにしています。

#coding: UTF-8

n = int(input())
a = list(map(int, input().split()))
k = int(input())

def bubunnwa(i,sum,b):
    if(i < n):
        b.append(0)
        bubunnwa(i+1,sum,b)
        del b[i:]
        b.append(1)
        bubunnwa(i+1,sum+a[i],b)
    elif(i == n and sum == k):
        print(b)





bd= []
bubunnwa(0,0,bd)

 

実行結果

　入力は1行目が数字の個数、2行目が使える数字の一覧、3行目が作りたい数字になっています。

　出力は、使ったか使ってないかを1か0で表しています。

・入力1

5
4 9 2 8 7
14

・出力1

[1, 0, 1, 1, 0]

・入力2

5
1 2 3 4 5
3

・出力2

[0, 0, 1, 0, 0]
[1, 1, 0, 0, 0]

終わりに

　ちょっとDPもできるように頑張ってみようと思います。