Clever Geek Handbook

Given a finite set of sorted real numbers, print all possible subsets whose sum is <= k

I would like to know if there are algorithms that solve this problem. This is a bit like a backpack 0-1 issue or a power setting issue, however it is different.

Given a finite set of sorted real numbers, we need to generate all possible subsets whose sum is <= k. Here k is real, the sorted real numbers are positive. For example, array = {1.48, 2.21 3.07, 4.35, 4.46} and k = 5.94. Output: {4.46}, {4.46, 1.48}, {4.35}, {4.35, 1.48}, {3.07}, {3.07, 2.21}, {2.21}, {2.21, 1.48} and {1.48}.

One way to solve is to just go from the highest number {4.46} to see how much you can include in the basket and then continue with the next bottom number {4.35} and so on. Is there an efficient way to do this? let me know

+3


source share


2 answers


A greedy algorithm can definitely work. To take advantage of the fact that the input is sorted, you can use a binary search.

The basic idea is this: first find the largest number in the array less than K by binary search, push an element of the result onto the stack, then recursively search the subframe that ends on that element for the sum of K - the value of that element. After that, search the subarray for the sum K to cover situations in which that item is not selected.



Sample code:

void boundedSumSubarray(float * arr, int size, float K, stack S) {
    int pos=binarySearch(arr,size,K);
    if (pos>=0) {
        pushStack(S,arr[pos]);
        boundedSumSubarray(arr,pos-1,K-arr[pos],S);
        popStack(S);
        boundedSumSubarray(arr,pos-1,K,S);
    } else
        printStack(S);
}
+4


source


You need to "generate" all subsets, not "count" all subsets. This makes the job easier :)

Let F (x, y, k) be the set of subsets x [1: k] whose sum is less than y.

F(x,y,k+1) = F(x,y,k) \union { for each set g in F(x,y-x[k+1], k): g \union {k+1} }


Use the above recursion to generate all such cases.

Note that you don't really need to recalculate the set of subsets when you do F(x,y-x[k+1], k)

. Just save the list in a tree structure.

If the number of subsets you expect is m, then this algorithm is O (nm).

+1


source






More articles:


All Articles