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

[Kate]

Помогите, пожалуйста, с программой!сама в паскале практически не разбираюсь, поэтому самой как то все сложно!
Задание:Разработать программу, которая делит N предметов с различными весами на две группы так, чтобы общие веса двух групп были максимально близки. Программа должна иметь развитый интерфейс пользователя.

(искала в ин-те,в книгах разных о паскале ничего не нашла)

[klem4]

Как вариант :

Сортируешь массив, далее берешь наибольший элемент кладешь в первую группу, далее кладешь оставшиеся элементы во вторую группу, пока ее суммарный вес не будет отличаться от веса первой группы нанекую дельту, далее начинаешь проделывать тоже самое с первой группой ...

[Гость]

Спасибо, конечно огромное, но это итак логично, вопрос в другом, как это написать в программу?(я писать программы не умею, а логика то есть)javascript:emoticon(':)', 'smid_1')

[klem4]

или скорее так : Текущий максимальный кладем в группу A, слудующий за ним кладем в B, далее начинаем прибявлять в B элементы с конца (с минимального) пока не достигнем (превысим) некой дельты в разностях весов групп. И так далее ...

[Lapp]

Спасибо, конечно огромное, но это итак логично, вопрос в другом, как это написать в программу?(я писать программы не умею, а логика то есть)javascript:emoticon(':)', 'smid_1')

Kate, если есть логика - давай ее сюда. Лично мне задача не кажется совсем тривиальной (я имею в виду именно логику). А вот прогу написать по готовому алгритму - это действительно пустяк.. Так что давай, опиши здесь свои наработки, а мы поможем с программированием этого.

2 klem4: мне кажется, без полного перебора тут не обойтись.. А это потребует ох, немалого времени! надо покумекать над оптимизацией..

[Kate]

Не очень понимаю...
сама я ничего не понимаю, что я думала приблизительно описал klem4(первый вариант).
В ин-те нашла какой то бред, сама ничего в этом не понимаю:
(может поможет)
"Алгоритмически":
Создаем 2 переменные и массив N элементов:
1-я переменная - общий вес первой группы
2-я переменная - общий вес второй группы
Каждый элемент массива (байт) - признак текущего веса предмета - скажем - 0 - он еще не распределен, 1-он уже переложен в 1-ю группу, 2-он уже переложен во 2-ю группу
1. находим максимальный элемент массива, у которого признак - 0
2. Если 1-я переменная (общий вес) больше 2-й, то 2-я переменная увеличиваеться на Ai (массу предмета), выставляеться признак 2 в массиве признаков
иначе 1-я увеличиваеться и выставляется признак 1
3. Проверяем массив признаков на наличие нулей - если есть, идем на пункт 1
4. Из массива признаков определяем, что куда переложили.

[Lapp]

1. находим максимальный элемент массива, у которого признак - 0
2. Если 1-я переменная (общий вес) больше 2-й, то 2-я переменная увеличиваеться на Ai (массу предмета), выставляеться признак 2 в массиве признаков
иначе 1-я увеличиваеться и выставляется признак 1

Иначе говоря, идем сверху вниз по весу предметов и кладем в кучку с меньшим весом.
Я не могу сказать, что этот способ верен, хотя похоже на правду..

[Kate]

Другого я не знаю, а как насчет программки?

[volvo]

Kate, я бы не торопился с программкой...

lapp прав, это насколько я понимаю, не совсем то, что нужно... По-моему, тот алгоритм, что ты привела, рассматривается на AlgoList-е для случая, когда требуется чтобы веса куч отличались не более чем в 2 раза (и второй вариант - в полтора)... А вот в случае, когда кучки должны быть максимально близки по весу - это задача упаковки, там как мне кажется надо по другому решать...

[мисс_граффити]

Плохо искали, наверное.
http://www.intuit.ru/department/pl/plpasca...plpascal_9.html
думаю, всем будет интересно почитать....

интерфейс пользователя уж как-нибудь сами.

Сообщение отредактировано: мисс_граффити - 13.07.2006 18:10

[Archon]

мисс_граффити, респект. Хорошая вещь, кинул в букмарки.

[Kate]

интерфейс пользователя уж как-нибудь сами.

с этим то и проблема, я не понимаю какие буквы там что обозначают, что вводить то как количество k или d.
и какой массив?
я честно пыталась понять но.....

[Archon]

Тебе с рекурсией или нет?

[мисс_граффити]

сразу бы и писали, что Вам нужно:
1) разработка алгоритма
2) написание программы с подробными комментариями
(первые 2 пункта в той статье выполнены)
3) подробное объяснение (видимо построчное)

надо было в "задачи на заказ". имхо.

[Kate]

Люди, спасибо вам всем, за ваш нелегкий труд!
дпльше как-нибудь сама попробую, частично уже написала....