给定数组形式的未排序整数集,找到大于或等于const整数x
的最小子集和。
例如: - 我们的集合是{4 5 8 10 10}
和x=15
所以最接近x
和>=x is {5 10}
的子集和
我只能想到一个简单的算法,它列出了集合的所有子集,并检查子集的总和是否为>=x
和最小值,但是它的指数算法并且列出所有子集需要O(2 ^ N)。我可以使用动态编程在多项式时间内解决它吗?
如果你所有数字的总和是S
,你的目标数是X
,你可以改为这样的问题:你能选择小于或等于S-X
的最大数字子集吗?
你有一个knapsack problem的特殊情况,重量和价值相等。
这是坏消息,因为这意味着你的问题是NP难的,但从好的方面来说,你可以使用KP的动态编程解决方案(仍然不是多项式)。或者你可以尝试KP的多项式近似,如果这对你来说足够好的话。
如前所述,这是NP完全的。另一种观察方式是,如果可以在多项式时间内解决这个问题,那么子集和问题也可以在多项式时间内求解(如果存在解,那么它将是相同的)。