Пожалуйста,помогите!, деление предметов на две группы,суммы которых максимально близки |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Пожалуйста,помогите!, деление предметов на две группы,суммы которых максимально близки |
Kate |
Сообщение
#1
|
Группа: Пользователи Сообщений: 5 Пол: Женский Репутация: 0 |
Помогите, пожалуйста, с программой!сама в паскале практически не разбираюсь, поэтому самой как то все сложно!
Задание:Разработать программу, которая делит N предметов с различными весами на две группы так, чтобы общие веса двух групп были максимально близки. Программа должна иметь развитый интерфейс пользователя. (искала в ин-те,в книгах разных о паскале ничего не нашла) |
klem4 |
Сообщение
#2
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Как вариант :
Сортируешь массив, далее берешь наибольший элемент кладешь в первую группу, далее кладешь оставшиеся элементы во вторую группу, пока ее суммарный вес не будет отличаться от веса первой группы нанекую дельту, далее начинаешь проделывать тоже самое с первой группой ... -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Гость |
Сообщение
#3
|
Гость |
Спасибо, конечно огромное, но это итак логично, вопрос в другом, как это написать в программу?(я писать программы не умею, а логика то есть)javascript:emoticon(':)', 'smid_1')
|
klem4 |
Сообщение
#4
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
или скорее так : Текущий максимальный кладем в группу A, слудующий за ним кладем в B, далее начинаем прибявлять в B элементы с конца (с минимального) пока не достигнем (превысим) некой дельты в разностях весов групп. И так далее ... -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Lapp |
Сообщение
#5
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Спасибо, конечно огромное, но это итак логично, вопрос в другом, как это написать в программу?(я писать программы не умею, а логика то есть)javascript:emoticon(':)', 'smid_1') Kate, если есть логика - давай ее сюда. Лично мне задача не кажется совсем тривиальной (я имею в виду именно логику). А вот прогу написать по готовому алгритму - это действительно пустяк.. Так что давай, опиши здесь свои наработки, а мы поможем с программированием этого. 2 klem4: мне кажется, без полного перебора тут не обойтись.. А это потребует ох, немалого времени! надо покумекать над оптимизацией.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Kate |
Сообщение
#6
|
Группа: Пользователи Сообщений: 5 Пол: Женский Репутация: 0 |
Не очень понимаю...
сама я ничего не понимаю, что я думала приблизительно описал klem4(первый вариант). В ин-те нашла какой то бред, сама ничего в этом не понимаю: (может поможет) "Алгоритмически": Создаем 2 переменные и массив N элементов: 1-я переменная - общий вес первой группы 2-я переменная - общий вес второй группы Каждый элемент массива (байт) - признак текущего веса предмета - скажем - 0 - он еще не распределен, 1-он уже переложен в 1-ю группу, 2-он уже переложен во 2-ю группу 1. находим максимальный элемент массива, у которого признак - 0 2. Если 1-я переменная (общий вес) больше 2-й, то 2-я переменная увеличиваеться на Ai (массу предмета), выставляеться признак 2 в массиве признаков иначе 1-я увеличиваеться и выставляется признак 1 3. Проверяем массив признаков на наличие нулей - если есть, идем на пункт 1 4. Из массива признаков определяем, что куда переложили. |
Lapp |
Сообщение
#7
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
1. находим максимальный элемент массива, у которого признак - 0 2. Если 1-я переменная (общий вес) больше 2-й, то 2-я переменная увеличиваеться на Ai (массу предмета), выставляеться признак 2 в массиве признаков иначе 1-я увеличиваеться и выставляется признак 1 Иначе говоря, идем сверху вниз по весу предметов и кладем в кучку с меньшим весом. Я не могу сказать, что этот способ верен, хотя похоже на правду.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Kate |
Сообщение
#8
|
Группа: Пользователи Сообщений: 5 Пол: Женский Репутация: 0 |
Другого я не знаю, а как насчет программки?
|
volvo |
Сообщение
#9
|
Гость |
Kate, я бы не торопился с программкой...
lapp прав, это насколько я понимаю, не совсем то, что нужно... По-моему, тот алгоритм, что ты привела, рассматривается на AlgoList-е для случая, когда требуется чтобы веса куч отличались не более чем в 2 раза (и второй вариант - в полтора)... А вот в случае, когда кучки должны быть максимально близки по весу - это задача упаковки, там как мне кажется надо по другому решать... |
мисс_граффити |
Сообщение
#10
|
просто человек Группа: Пользователи Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
Плохо искали, наверное.
http://www.intuit.ru/department/pl/plpasca...plpascal_9.html думаю, всем будет интересно почитать.... интерфейс пользователя уж как-нибудь сами. Сообщение отредактировано: мисс_граффити - -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
Archon |
Сообщение
#11
|
Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
мисс_граффити, респект. Хорошая вещь, кинул в букмарки.
-------------------- Close the World...txeN eht nepO
|
Kate |
Сообщение
#12
|
Группа: Пользователи Сообщений: 5 Пол: Женский Репутация: 0 |
интерфейс пользователя уж как-нибудь сами. с этим то и проблема, я не понимаю какие буквы там что обозначают, что вводить то как количество k или d. и какой массив? я честно пыталась понять но..... |
Archon |
Сообщение
#13
|
Профи Группа: Пользователи Сообщений: 618 Пол: Мужской Репутация: 24 |
Тебе с рекурсией или нет?
-------------------- Close the World...txeN eht nepO
|
мисс_граффити |
Сообщение
#14
|
просто человек Группа: Пользователи Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
сразу бы и писали, что Вам нужно:
1) разработка алгоритма 2) написание программы с подробными комментариями (первые 2 пункта в той статье выполнены) 3) подробное объяснение (видимо построчное) надо было в "задачи на заказ". имхо. -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
Kate |
Сообщение
#15
|
Группа: Пользователи Сообщений: 5 Пол: Женский Репутация: 0 |
Люди, спасибо вам всем, за ваш нелегкий труд!
дпльше как-нибудь сама попробую, частично уже написала.... |
Текстовая версия | 7.10.2024 11:24 |