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

Question

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

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

的最小子集总和

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

Answer 1

如果你所有数字的总和是S，而你的目标数字是X，你可以这样改写这个问题：你能选择数字中小于的最大子集吗大于或等于 S-X?

你有一个 knapsack problem 的特例，其中权重和值相等。

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

Answer 2

如前所述，这是 NP 完全的。另一种看法是，如果可以在多项式时间内解决这个问题，那么子集和问题也可以在多项式时间内解决（如果存在解决方案则相同）。

Answer 3

我认为其他答案不正确。您的问题实际上是 0-1 背包问题（即没有重复）的变体 solvable in polynomial time with dynamic programming。您只需要按照@biziclop 的回答制定您的标准。

Answer 4

贪婪的方法怎么样？

首先我们按降序对列表进行排序。然后我们递归地弹出排序列表的第一个元素，从x中减去它的值，并重复直到x等于或小于0。

在伪代码中：

sort(array)
current = 0
solution = []
while current < x:
    if len(array) < 0:
        return -1 //no solution possible
    current += array[0]
    solution.append(array.pop(0))
return solution

Answer 5

我正在修改DP。我想到了这个问题。然后我搜索并得到了这个问题，但没有正确的答案。

所以这是完整代码（以及注释）：希望它有用。

sample image of table //与子集和的概念完全相同（找到子集和的最小差）

public class Main
{
public static int minSubSetSum(int[] arr,int n,int sum,int x){
    boolean[][] t=new boolean[n+1][sum+1];
    //initailization if n=0 return false;
        for(int i=0;i<sum+1;i++)
            t[0][i]=false;
    //initialization if sum=0 return true because of empty set (a set can be empty)
        for(int i=0;i<n+1;i++)
            t[i][0]=true;   //here if(n==0 && sum==0 return true) has been also initialized
    
    //now DP top-down
    
    for(int i=1;i<n+1;i++)
        for(int j=1;j<sum+1;j++)
        {
            if(arr[i-1]<=j)
                t[i][j]=t[i-1][j-arr[i-1]] || t[i-1][j]; // either include arr[i-1] or not 
            else
                t[i][j]=t[i-1][j]; //not including arr[i-1] so sum is not deducted from j
        }
        
    //now as per question we have to take all element as it can be present in set1
    //if not in set1 then in set2 ,so always all element will be a member of either set
    // so we will look into last row(when i=n) and we have to find min_sum(j)
    
    int min_sum=Integer.MAX_VALUE;
    for(int j=x;j<=sum;j++)
        if(t[n][j]==true){      //if in last row(n) w.r.t J , if the corresponding value true then
            min_sum=j;    //then that sum is possible
            break;
            }
            
    if(min_sum==Integer.MAX_VALUE)
        return -1;// because that is not possible
        
    return min_sum;
}
public static void main(String[] args) {
    int[] arr=new int[]{4,5,8,10,10};
    int x=15;
    int n=arr.length;
    int sum=0;
    for(int i=0;i<n;i++)
        sum=sum+arr[i];
   System.out.println("Min sum can formed greater than X is");
   
   int min_sum=minSubSetSum(arr,n,sum,x);
   System.out.println(min_sum);
    
}

}

由于问题是 N-P 完全的，所以 DP 时间复杂度减少到 T(n)=O(n*总和) space 复杂度 =O(n*sum);

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

Given a list of n integers , find the minimum subset sum greater than X

arrays

algorithm

subset

dynamic-programming

subset-sum