arrays - 给定一个包含 n 个整数的列表，找到大于 X 的最小子集和

Question

给定一组未排序的数组形式的整数，找到大于或等于常量整数 x 的最小子集和。

例如:- 我们的集合是 {4 5 8 10 10} 和 x=15所以最接近 x 和 >=x 的最小子集和是 {5 10}

我只能想到一个简单的算法，它列出集合的所有子集并检查子集的总和是否为 >=x 以及是否为最小值，但它是一个指数算法并列出所有子集需要O(2^N)。我可以使用动态规划在多项式时间内求解吗？

Answer 1

如果你所有数字的总和是S，而你的目标数字是X，你可以这样改写这个问题:你能选择小于或等于 S-X 的数字？

你有一个特殊情况 knapsack problem ，其中权重和值相等。

这是个坏消息，因为这意味着您的问题是 NP-hard，但从好的方面来说，您可以只使用 KP 的动态规划解决方案(它仍然不是多项式)。或者您可以尝试 KP 的多项式逼近，如果这对您来说足够好的话。