（別のSO質問へのリンクを返信するか、これを重複して閉じる前に、質問を注意深く読んでください。これは、この問題の標準的なバリアントとは異なり、長い間検索してきたので、存在しないと確信しています。ここにこのような質問はありません）
X[i]のサブセットの合計である可能な最小のSが>=T（完全なセットの合計よりも小さいいくつかのターゲット値）であるかどうかを見つける必要があります。
セットはそれほど大きくはありませんが（約40要素）、指数関数的なバックトラッキングソリューションには大きすぎます。
数と合計が膨大であるため（約10 ^ 15）、動的計画法は機能しません（可能な状態の数が多いため、メモ化テーブルのメモリがすぐに不足します）。
同じ理由で、Pisingerによる線形時間アルゴリズムは機能しません（これはO（nr）であり、rは合計の上限であり、この場合は大きすぎます）。
合計が大きいが数が少ないこの場合に役立つ決定論的アルゴリズムはありますか？近似アルゴリズムに頼りたくありません。
上記の条件を考えると、分枝限定法を使用したバックトラックソリューションが、正確なソリューションを取得するための最良の方法であると思います。
アイデアはすべてのサブセットをチェックすることですが、アルゴリズムの実行中にいくつかの可能なサブセットの計算ツリーをトリミングすることができます。
たとえば、を探していてS = 10^8、の解決策をすでに見つけていると仮定しますsol=10^8 + 10^7。ここで、いくつかのスーパーセットであるすべてのサブセットをチェックしているXと、それがわかりますsum(X) = 10^9。を含むサブセットをチェックし続ける必要はありXません。それらをスキップするだけで、最適化されません。
また、ソリューションを並列化しようとします。通常、分枝限定法は簡単に並列化されます。たまに新しい最良のソリューションを同期する必要があります。
あなたが言ったように、セットはそれほど大きくはありませんでした (約 40)。複雑さの古典的な指数時間アルゴリズムがO(2^(n/2) n)あなたのニーズに合うと思いますhttp://en.wikipedia.org/wiki/Subset_sum_problem#Exponential_time_algorithm。
ここでアプローチを簡単に説明できます。セットを 2 つの等しいサイズのセット (たとえば A と B) に分割します。そして、それらのサブセットの合計を列挙して、サイズの 2 つのセット ( 2^(n/2)PA と PB など) を生成します。次に、PA と PB を並べ替え、二分探索を使用してT、時間を超える合計を見つけることができますO(2^(n/2) n)。