给定数组形式的未排序整数集，找到大于或等于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完全的。另一种观察方式是，如果可以在多项式时间内解决这个问题，那么子集和问题也可以在多项式时间内求解（如果存在解，那么它将是相同的）。