Равномерное распределение сумм

  1. 8 г. назад
    14.09.2016 10:38:12 отредактировано ЗлобнийМальчик

    Всем привет. Подскажите пожалуйста алгоритм лучше перебора для следующей задачи: есть ряд положительных чисел. Необходимо разбить его на заданное число групп. При разбиении каждой группе следует ассоциировать число равное сумме всех компонентов группы. Задача разбиения заключается в том, чтобы самая разница между самой маленькой суммой и самой большой суммой были минимальны
    Пример.
    Ряд чисел
    1 10 12 13 1000
    Число групп - 2
    Правильный результат разбиения
    Группа 1:
    Компоненты: 1000
    Сумма: 1000
    Группа 2:
    Компоненты: 1 10 12 13
    Сумма: 1 + 10 +12 +13 = 36
    Разница = 1000 - 36 => 964
    Неправильный результат разбиения
    Группа 1:
    Компоненты: 1000 13
    Сумма: 1013
    Группа 2:
    Компоненты: 1 10 12
    Сумма: 1 + 10 +12 = 23
    Разница = 1013 - 23 => 990 - больше чем 964
    Пробовал монте карло - не очень качественно разбивает. К самой большой группе обычно что то лишнее добавляется

  2. -image-

    Кто сделает ему работу бесплатно, тот - лох!

    Ответы: (2)
  3. (1) и вам спасибо

  4. как я понимаю -- это подзадача?
    если да, то опиши изначальную

    Ответы: (14)
  5. 14.09.2016 12:04:55 отредактировано sf

    а перебором это как?

    Ответы: (5) (16)
  6. (4) Неверно
    6
    4
    2
    2
    1

    Ответы: (6)
  7. 14.09.2016 12:08:46 отредактировано sf

    (5) да, я понял уже. все проще

  8. ого, афоня протрезвел

    Ответы: (8)
  9. (7) он не нарочно

  10. 14.09.2016 14:53:10 отредактировано sda553

    Опишу алгоритм так
    НаборЧисел. Отсортировать(убыв)
    Для каждого ТекущееЧисло из НаборЧисел Цикл
    Группа = НайтиГруппуСНайменьшейТекСуммой()
    Группа.Добавить(ТекущееЧисло)
    КонецЦикла

    Ответы: (10) (15)
  11. (9) Ничо не понял.
    На входе НаборЧисел, ЧислоГрупп.
    На выходе НаборГрупп;

    НаборЧисел.Отсортировать("Убыв");
    Для каждого ТекущееЧисло из НаборЧисел Цикл
    Группа = НайтиГруппуСНайменьшейТекСуммой();
    Группа.Добавить(ТекущееЧисло);
    КонецЦикла;

    Для первой итерации НаборГрупп - пустой массив. Что ты там искать собрался?
    Где заполнение НаборГрупп?

    Давай не отлынивай. Ты же тут самый умный по части точных наук.

    Ответы: (13)
  12. 14.09.2016 15:48:34 отредактировано jsmith82

    Чет тип того, если развивать твою мысль.

    НаборГрупп = Новый Массив();
    Для Итер = 1 По ЧислоГрупп Цикл
    НаборГрупп.Добавить(Новый Массив(());
    КонецЦикла;

    НаборЧисел.Отсортировать("Убыв");

    Пока НаборЧисел.Количество() > 0 Цикл
    Пока Истина Цикл
    Если Набор.Чисел.Количество() > 0 Тогда
    Группа = НайтиГруппуСНайменьшейТекСуммой();
    Группа.Добавить(НаборЧисел.Поп());
    Иначе
    Прервать;
    КонецЕсли;
    КонецЦикла;
    КонецЦикла;

  13. а чо это типа алкашь с нами не общается по трезвяне?

  14. 14.09.2016 16:05:07 отредактировано sda553

    jsmith82 Давай не отлынивай. Ты же тут самый умный по части точных наук.

    я алгоритм подсказал, а реализация уже за автором, буду я еще инициализацией переменных заниматься

  15. 14.09.2016 23:46:02 отредактировано ЗлобнийМальчик

    zak555 как я понимаю -- это подзадача?
    если да, то опиши изначальную

    ну. если очень хочется, то я могу(упрощённо естественно)
    В таблице есть записи у которых определённая колонка имеет значение истина. необходимо эти записи записать в другую таблицу используя параллельные процессы (я не знаю какой правильный аналог в 1С - фоновые задачи может быть?) в таблице также имеется колонка месяц_года (по типу 201608 - это август 2016) по которым хочется эти записи разбить так, чтобы несколько фоновых задач могли параллельно эти записи считывать и записывать. необходимо распределить записи по параллельным фоновым задачам так, чтобы они приблизительно в одно время закончили свою работу (исходных и целевых таблиц несколько)

  16. 14.09.2016 23:52:00 отредактировано ЗлобнийМальчик

    sda553 Опишу алгоритм так
    НаборЧисел. Отсортировать(убыв)
    Для каждого ТекущееЧисло из НаборЧисел Цикл
    Группа = НайтиГруппуСНайменьшейТекСуммой()
    Группа.Добавить(ТекущееЧисло)
    КонецЦикла

    спасибо. Я тоже сегодня к этому алгоритму пришел. Для меня правда неочевидно то, что это оптиум - но интуитивно я считаю, что это так.

    Ответы: (18)
  17. sf а перебором это как?

    ну как. получаем все возможные комбинации всех элементов и смотрим, какая из комбинаций имеет наименьшее значение функции оптиума

    Ответы: (17)
  18. (16) Та ну пистец.

  19. (15) методом матиндукции доказывается.
    1. если групп столько же сколько чисел, то очевидно, алгоритм разложит в каждую группу по отдельному числу и это будет оптимум
    2. Допускаем, что для n чисел алгоритм дает оптимум
    3. Смотрим n+1 случай. Раскладываем их по алгоритму. Убираем минимальное число, оставляем n. Исходя из 2 это оптимум. Добавление оптимум еще оптимумее делает. И останется доказать, что если убрать не минимальное, то будет ни фига не опттмум. Это тебе уже на домашнее задание оставим

или зарегистрируйтесь чтобы ответить!