部分和問題（N個の配列から和がKになるように選ぶ）とその解き方

部分和問題（N個の配列から和がKになるように選ぶ）とその解き方

部分和問題とは、\(N\) 個の数 \( a_1, a_2, ..., a_n\) が与えられたとき、その中からいくつかを選んで和をちょうど \(K\) にできるか判定をする問題です。 例えば配列が [1,3,8] で、\(K\) が 9 のときは、1,8 を選ぶと和が 9 になり K に一致します。 全探索による単純なアルゴリズムでは計算量が大きくなってしまいますが、\(K\)と \(N\) の

2020/09/23 14:44