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来将该精确查询减少到子集和。