3

Имеется исходный массив положительных чисел, N — число новых массивов, Mi – максимальная сумма в текущем массиве. Нужно распределить все числа из заданного массива на N массивов так, чтобы сумма чисел в каждом массиве была максимальна близка к заданной Mi. Найти оптимальный вариант распределения.

Я уверен, что должен быть готовый алгоритм подобной задачи. Что-то из разряда комбинаторной оптимизации может быть. Перебор не предлагать

11
  • 1
    Условия задачи точно корректно написал? 28 дек 2016 в 6:15
  • Да. Mi может быть свое для каждого массива 28 дек 2016 в 6:21
  • в новых массивах может быть использовано одновременно одно и то же число из исходного массива?
    – Grundy
    28 дек 2016 в 7:06
  • Классическая "задача о рюкзаке". И решения тоже классические.
    – Akina
    28 дек 2016 в 7:06
  • 1
    У Вас просто вырожденная задача, когда все веса равны единице.
    – Akina
    28 дек 2016 в 7:20

1 ответ 1

1
  1. Если общее количество чисел равно N*Mi, то в качестве критерия оптимальности можно принять минимум суммы квадратов отклонений фактического Mi от требуемого.
  2. Заполнять каждый массив следует от больших чисел к меньшим ("жадный" алгоритм), рассматривая варианты с перебором и недобором по каждому массиву.
  3. Не думаю, что за обозримое время можно достичь большего даже при относительно небольших массивах.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.