There is an initial array of positive numbers, N is the number of new arrays, Mi is the maximum amount in the current array. It is necessary to distribute all the numbers from the given array into N arrays so that the sum of the numbers in each array is maximally close to the given Mi Find the best distribution option.

I am sure that there should be a ready algorithm for a similar task. Something from the category of combinatorial optimization can be. Brute force does not offer

  • one
    Problem conditions exactly correctly written? - Alexander Puzanov
  • Yes. Mi may have its own for each array - Sergey
  • in the new arrays can be used simultaneously the same number from the original array? - Grundy
  • The classic "backpack problem". And the solutions are also classic. - Akina
  • one
    You simply have a degenerate task, when all the weights are equal to one. - Akina

1 answer 1

  1. If the total number of numbers is N * Mi, then as the optimality criterion we can take the minimum of the sum of squares of deviations of the actual Mi from the required one.
  2. Each array should be populated from large numbers to smaller ones (the “greedy” algorithm), considering options with over and under-recruitment for each array.
  3. I do not think that in the foreseeable time it is possible to achieve more even with relatively small arrays.