(別のSO質問へのリンクを返信するか、これを重複して閉じる前に、質問を注意深く読んでください。これは、この問題の標準的なバリアントとは異なり、長い間検索してきたので、存在しないと確信しています。ここにこのような質問はありません)
X[i]のサブセットの合計である可能な最小のSが>=T(完全なセットの合計よりも小さいいくつかのターゲット値)であるかどうかを見つける必要があります。
セットはそれほど大きくはありませんが(約40要素)、指数関数的なバックトラッキングソリューションには大きすぎます。
数と合計が膨大であるため(約10 ^ 15)、動的計画法は機能しません(可能な状態の数が多いため、メモ化テーブルのメモリがすぐに不足します)。
同じ理由で、Pisingerによる線形時間アルゴリズムは機能しません(これはO(nr)であり、rは合計の上限であり、この場合は大きすぎます)。
合計が大きいが数が少ないこの場合に役立つ決定論的アルゴリズムはありますか?近似アルゴリズムに頼りたくありません。