给定n个整数的列表，找到大于X的最小子集和 [英] Given a list of n integers , find the minimum subset sum greater than X

问题描述

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

Given an unsorted set of integers in the form of array, find minimum subset sum greater than or equal to a const integer x.

例如：-我们的集合是 {4 5 8 10 10} 和 x = 15
，因此最接近 x 和> = x的最小子集总和为{5 10}

eg:- Our set is {4 5 8 10 10} and x=15 so the minimum subset sum closest to x and >=x is {5 10}

我只能想到一个天真的算法，该算法列出了集合的所有子集，并检查子集的总和是否为> = x 是否为最小值，但是其指数算法并列出所有子集需要O（2 ^ N）。我可以使用动态编程在多项式时间内求解吗？

I can only think of a naive algorithm which lists all the subsets of set and checks if sum of subset is >=x and minimum or not, but its an exponential algorithm and listing all subsets requires O(2^N). Can I use dynamic programming to solve it in polynomial time?

推荐答案

如果所有数字的总和为 S ，而您的目标数字是 X ，则可以改写这样的问题：是否可以选择较小的数字的最大子集等于或等于 SX ？

If the sum of all your numbers is S, and your target number is X, you can rephrase the question like this: can you choose the maximum subset of the numbers that is less than or equal to S-X?

并且您有背包问题，其中重量和价值相等。

And you've got a special case of the knapsack problem, where weight and value are equal.

这是个坏消息，因为这意味着您的问题是NP难题，但从好的方面来说，您可以使用KP的动态编程解决方案（仍然是t多项式）。或者，也可以尝试KP的多项式近似，如果这样对您足够的话。

Which is bad news, because it means your problem is NP-hard, but on the upside you can just use the dynamic programming solution of the KP (which still isn't polynomial). Or you can try a polynomial approximation of the KP, if that's good enough for you.

这篇关于给定n个整数的列表，找到大于X的最小子集和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！