Given an array of n numbers A1, A2, ...An, how many maximum groups I can form from this array, such that the sum of the elements in each group is ≥ X?
Constraints: N ≤ 106, X ≤ 106, 0 ≤ Ai ≤ X, Sum of all Ai's ≤ 106.
For example if Array is
[5, 5, 9, 5, 12, 5] and X is 20. Answer is 2 as we can form 2 groups [5,5,5,5] and [9, 12] such that both groups have sum greater than or equal to 20
I have no idea how to get the optimal solution, Any help is welcome.
Thanks!!
This seems to be (at least) as hard as https://en.wikipedia.org/wiki/Bin_packing_problem. To see this, suppose that the sum of the numbers is divisible by X. The upper bound for the answer is (Sum / X). To obtain exactly (Sum / X) means to pack all the values perfectly in bins of volume X.
I still didn't get the reduction. In bin-packing problem we try to minimize the numbers of bins also each bins have constraint on upper limit. Here we are trying to maximize the number of bins and there is lower limit in each bin, Can you please explain your deduction?
It's not a proper reduction per se. It just shows that there are instances of your problem that are hard instances of the bin packing problem.
Consider the case when X is equal to half the sum of all numbers. Then, the answer to your problem may only be 1 or 2. It is 2 only if you can split the numbers into two subsets of sum X. This split is also the only way of packing the numbers into 2 bins of volume X (as opposed to 3 or more).
More generally, I'm using the fact that for tests with Sum = K * X, K is an upper bound for your original problem and a lower bound for the bin packing problem. Obviously, for both of these problems, you should know how to check for a solution that meets the lower/upper bound. For this type of test, the decision problem of checking the optimal bound is identical: "Can we fit everything into K subsets of sum exactly X?".
So you have instances of your problem that are tight instances of bin-packing. They are somewhat specific instances, but I don't think they're easier in any significant way. Already for K = 2, it's a knapsack problem with capacity set to half the sum of weights. I don't know an algorithm that makes use of this particular capacity.
May you please share the link to this problem in order to be able to test our solutions?
Sorry, I don't have any link
OK, don't care, Thank you :D