0,1揹包減少子集總和

Question

我知道如何將子集和減少到0,1揹包。但是是否有可能將揹包減少到子集總和？怎麼樣？

Answer 1

在論文"Reducing a Target Interval to a Few Exact Queries"的定理2中描述了從0,1揹包到子集和的減少。它分三步進行。首先，將揹包減少到一個決策問題，該問題測試是否存在一個權重最大爲b且值至少爲t的子集。這可以通過對閾值進行二分搜索來完成。其次，將這個決策問題減少到一小組確切的查詢形式「是否有一個子集，權重完全是b，值恰好是t？」這是一個巧妙的減少，不需要枚舉所有可能的b和t。第三，通過將每個（權重，值）對映射到整數（權重* C +值）足夠大的C來將該精確查詢減少到子集和。