多項式アルゴリズム

Question

任意の（整数）金額のそれぞれのn個のチェックが、同じ金額の2つの部分にチェックを分割できるかどうかを判断すると、

私はこの問題を解決する方法を忘れています。これを多項式時間で解くアルゴリズムはありますか？これはNP完全ですか？

Answer 1

はい、NP完全な問題です。それはthe subset sum problemのバリエーションです。

Answer 2

実際には、動的プログラミングを使ってO（n * sum/2）でこれを解くことができます。まずすべてのチェックをvaraibel sumに集計し、チェック値にdpを実行しますその合計がs/2に等しいかどうかを最後にチェックする。