java - 整数の配列で合計が特定の数になる最小セットを見つける

Question

合計 s と正の整数の配列を指定して、要素の合計が s になる最小部分集合を見つけます。たとえば、配列 {1,2,3,4,5} と合計 s = 8 の場合、最小サブセットは {3,5} になります。

これまでのところ、再帰を使用した貪欲なアプローチで配列に加算される整数のセットを解決できますが、最小サブセットを見つける方法を見つけることができません。調査すべき特定のアルゴリズムはありますか?

Answer 1

これが「ゼロワン平等ナップザック問題」です。NP完全です。しかし、この問題に対して有効なアルゴリズムは数多く存在します。

1. 合計がその数のメモリ ビットを割り当てて、それらを n (配列要素の数) 回反復するのに十分小さい場合は、動的計画法を使用できます。

2. CPLEX、Gurobi、SCIP などの混合整数プログラムソルバーは、実際に発生する可能性が高い「典型的な」インスタンスでかなりうまく機能することがよくあります。ナップザック問題を MIP ソルバーへの入力として定式化するときは、精度の問題を回避するために注意が必要です。

3. ある程度の不正確さを許容できる場合: 不等式ナップザックの多項式時間近似スキーム(最大で s に加算される最小の数値セットが必要な場合) が存在し、説明するのがそれほど難しくありません: 関連するすべての数値を何かにスケールダウンします。動的プログラミングを実行して結果を処理できる場所。近似問題の近似解も受け入れるように注意すれば、同じアプローチを使用して等式ナップザックの近似解を得ることができます。