0,1ナップザックからサブセットの合計への還元

Question

私はサブセットの合計を0,1回のナップザックに減らす方法を知っています。しかし、サブセット合計にナップザックを減らすことは可能ですか？どうやって？

Answer 1

0,1のナップサックからサブセットサムへの減少は、論文"Reducing a Target Interval to a Few Exact Queries"の定理2に記載されています。それは3つのステップで進行する。まず、重さがb以下で、値がt以上のサブセットが存在するかどうかをテストする決定問題にナップザックを減らします。これは、しきい値を超えるバイナリ検索によって実行できます。第2に、この決定問題を、「正確に重量がbで正確にtの部分集合がありますか？」という形式の正確なクエリの小さな集合に減らします。これは可能なすべてのbとtを列挙することを必要としない巧妙な削減です。第3に、十分な大きさのCに対して、各（重み、値）対を整数（重み* C +値）にマッピングすることによって、この正確なクエリを部分集合和に減らす。