Консультация № 18967
29.03.2005, 21:21
0.00 руб.
0 2 2
Здравствуйте.
Есть число предметов N и их веса: A1, A2, ... An.
Нужно разделить эти предметы на 2 группы так, чтобы общие веса этих групп были наиболее близки.
Как рационально можно это проделать?

Приложение:
предметы я представил как массив из чисел типа Integer, где значение каждого элемента = весу предмета

Обсуждение

Неизвестный
29.03.2005, 22:29
общий
это ответ
Здравствуйте, andrey!
Вычисляем общий вес. Сортируем, например по возрастанию. Получаем массив P1, ..., Pn. Пусть это будет первая группа. Из неё извлекаем во вторую группу предмет, вес которого наиболее близок к суммарному пополам(но меньше либо равен). Если разница равна нулю - поделили поровну, всё. Если нет, то из первой группы выбираем предмет (если есть, если нет - конец) наиболее близкий по весу к разнице весов первой и второй группы пополам (но меньше либо равно). И т. д., пока разница не станет <= 1 или не найдутся предметы с меньшим, чем необходимо весом.
P. S. Массив лучше отсортировать, чтобы быстрее работало. В итоге, первая группа не легче второй, но разница в весе минимальна.
Неизвестный
30.03.2005, 08:54
общий
это ответ
Здравствуйте, andrey!
1. Находим предмет с максимальным весом.
2. Если сумма весов в первой группе больше, добавляем его во вторую круппу.
Если меньше, добавляем его в первую группу,
Ну если равны - то тут по настроению
3. Если остался еще предмет - идем на пункт1.
"Алгоритмически":
Создаем 2 переменные и массив N элементов:
1-я переменная - общий вес первой группы
2-я переменная - общий вес второй группы
Каждый элемент массива (байт) - признак текущего веса предмета - скажем - 0 - он еще не распределен, 1-он уже переложен в 1-ю группу, 2-он уже переложен во 2-ю группу
1. находим максимальный элемент массива, у которого признак - 0
2. Если 1-я переменная (общий вес) больше 2-й, то 2-я переменная увеличиваеться на Ai (массу предмета), выставляеться признак 2 в массиве признаков
иначе 1-я увеличиваеться и выставляется признак 1
3. Проверяем массив признаков на наличие нулей - если есть, идем на пункт 1
4. Из массива признаков определяем, что куда переложили.
Форма ответа