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
source share
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); }
source share
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).
source share