IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Пожалуйста,помогите!, деление предметов на две группы,суммы которых максимально близки
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 5
Пол: Женский

Репутация: -  0  +


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

(искала в ин-те,в книгах разных о паскале ничего не нашла)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Как вариант :

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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






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


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +



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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Гость @ 12.07.2006 22:11) *

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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6





Группа: Пользователи
Сообщений: 5
Пол: Женский

Репутация: -  0  +


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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Kate @ 13.07.2006 9:32) *

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8





Группа: Пользователи
Сообщений: 5
Пол: Женский

Репутация: -  0  +


Другого я не знаю, а как насчет программки?
blush.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






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

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


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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

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

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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12





Группа: Пользователи
Сообщений: 5
Пол: Женский

Репутация: -  0  +



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

с этим то и проблема, я не понимаю какие буквы там что обозначают, что вводить то как количество k или d.
и какой массив?
я честно пыталась понять но..... wacko.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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

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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15





Группа: Пользователи
Сообщений: 5
Пол: Женский

Репутация: -  0  +


Люди, спасибо вам всем, за ваш нелегкий труд!
дпльше как-нибудь сама попробую, частично уже написала.... give_rose.gif give_rose.gif give_rose.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 19.09.2017 22:31
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"