Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

wannared's blog

An interesting problem
By wannared, history, 7 years ago, In English

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!!

  • Vote: I like it
  • +14
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

May you please share the link to this problem in order to be able to test our solutions?

→ Reply