問題
総当たり
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja
長さ n の数列 A と整数 m に対して、A の要素の中のいくつかの要素を足しあわせて m が作れるかどうかを判定するプログラムを作成してください。A の各要素は1度だけ使うことができます。
数列 A が与えられたうえで、質問として q 個の mi が与えれるので、それぞれについて "yes" または "no" と出力してください。
入力
1行目に n、2行目に A を表す n 個の整数、3行目に q、4行目に q 個の整数 miが与えられます。
出力
各質問について A の要素を足しあわせて mi を作ることができれば yes と、できなければ no と出力してください。
制約
n≤20
q≤200
1≤Aの要素≤2,000
1≤mi≤2,000
解法
def solve(i, target): global input_list if target == 0: return True if i >= len(input_list): return False res = solve(i + 1, target) or solve(i + 1, target - input_list[i]) return res target = 5 input_list = [1, 5, 7, 10, 21] solve(0, target) target = 4 input_list = [2, 4, 17, 8] solve(0, target) target = 25 input_list = [2, 4, 17, 8] solve(0, target)
solve(i,target)を「input配列のi番目以降の要素を使ってtargetを作れる場合Trueを返却する」メソッドとした場合、今回の問題設定では、solve(0,target)がTrueになるかどうかを調べることが課題となる。
そのため、まずsolve(0,target)を部分問題に分割し、solve(i+1,target)とsolve(i+1,target - input配列[i])のどちらかがTrueであれば、Trueが返却されるとする。
iをどんどん増やしていき、どこかのプロセスの分岐でtarget - input配列[i]=0となれば、返却値はTrueになり、targetを満たす組み合わせがあることがわかる。