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

Question

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

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}

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?

Answer 1

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.

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.

Answer 2

As already mentioned, this is NP-complete. Another way of seeing that is, if one can solve this in polynomial time, then subset-sum problem could also be solved in polynomial time (if solution exist then it will be same).

Answer 3

I believe the other answers are incorrect. Your problem is actually a variation of the 0-1 knapsack problem (i.e. without repetitions) which is solvable in polynomial time with dynamic programming. You just need to formulate your criteria as in @biziclop's answer.

Answer 4

How about a greedy approach?

First we sort the list in descending order. Then we recursively pop the first element of the sorted list, subtract its value from x, and repeat until x is 0 or less.

In pseudocode:

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

I was revising DP. I thought of this question. Then I searched and I get this question but without a proper answer.

So here is the complete code (along with comments ): Hope it is useful.

sample image of table //exactly same concept as subset-sum(find the minimum difference of subset-sum)

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);
    
}

}

As the problem was N-P complete so with DP time complexity reduces to T(n)=O(n*sum) and space complexity =O(n*sum);