Мастера DELPHI, Delphi programming community Рейтинг@Mail.ru Титульная страница Поиск, карта сайта Написать письмо 
| Новости |
Новости сайта
Поиск |
Поиск по лучшим сайтам о Delphi
FAQ |
Огромная база часто задаваемых вопросов и, конечно же, ответы к ним ;)
Статьи |
Подборка статей на самые разные темы. Все о DELPHI
Книги |
Новинки книжного рынка
Новости VCL
Обзор свежих компонент со всего мира, по-русски!
|
| Форумы
Здесь вы можете задать свой вопрос и наверняка получите ответ
| ЧАТ |
Место для общения :)
Орешник |
Коллекция курьезных вопросов из форумов
KOL и MCK |
KOL и MCK - Компактные программы на Delphi
Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / rsdn.org

 
Чтобы не потерять эту дискуссию, сделайте закладку « предыдущая ветвь | форум | следующая ветвь »

Задачка про яблоки и корзины


DayGaykin ©   (01.06.17 18:53

Есть N корзин и M яблок.

Пусть W[m] - вес яблока m.

Задача распределить яблоки по корзинам максимально справедливо. Другими словами, чтобы те кто понесут корзины считали, что распределение максимально справедливо и не ныли.

Два вопроса:
1. Какой критерий можно считать самым справедливым?
2. Как распределить согласно этому критерию?


Юрий Зотов ©   (01.06.17 19:02[1]

> 1. Какой критерий можно считать самым справедливым?

Оба не несут ничего и за это получают одинаковые деньги.

> 2. Как распределить согласно этому критерию?

Корзины и яблоки продать, а деньги поделить пополам.


Юрий Зотов ©   (01.06.17 19:04[2]

* Считая, что носильщиков двое. Если их больше - соответственно экстраполировать.


Dimka Maslov ©   (01.06.17 19:07[3]


> деньги поделить пополам.


Неправильный подход. Деньги недо отдать хозяину.


DayGaykin ©   (01.06.17 19:34[4]

Под звездочкой

Есть N корзин и M яблок. Яблоки делятся по сортам.

Пусть W[m] - вес яблока m.
Пусть S[m] - сорт яблок.

Задача распределить яблоки по корзинам максимально справедливо. Другими словами, чтобы те кто понесут корзины считали, что распределение максимально справедливо и не ныли.
При этом чем меньше разных сортов яблок в корзине, тем более корзинонос доволен.

Два вопроса:
1. Какой критерий можно считать самым справедливым и вызывающим наибольшее удовольствие?
2. Как распределить согласно этому критерию?


rrrrrr ©   (01.06.17 19:34[5]

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


rrrrrr ©   (01.06.17 19:36[6]

1. Какой критерий можно считать самым справедливым и вызывающим наибольшее удовольствие?

элементарно же.
такой при котором ни один не считает что его обули


Тимохов Дима ©   (01.06.17 21:31[7]

Очевидно, что справедливость = максимальная равность весов корзин.

Решение:
1. Сортируем яблоки по весу.
2. Кладем в корзины яблоки по порядку возрастания.
3. Потом кладем в корзины в обратном порядке корзин остальные яблоки в порядке возрастания.
4. И т.д. - чередуем в прямом порядке и в обратном порядке.

Если яблок много, корзин много, и яблоки это яблоки, а не мифические тела, которые весят от 1 в минус десятой грамма до 1 в плюс десятой грамма, то распределение яблок будет примерно одинаковым по весу.

Если яблок мало, корзин мало, то это уже дискретная математика. Терпеть ее не мог никогда....((( Тады не знаю.

ИМХО.


Тимохов Дима ©   (01.06.17 21:32[8]


> DayGaykin ©   (01.06.17 19:34) [4]

Аналогично [7].
Только сначала выполняем задачу для первого сорта.
Потом для второго.


rrrrrr ©   (01.06.17 21:52[9]

Очевидно, что справедливость = максимальная равность весов корзин.


их было четверо.
муж инвалид без руки, его жена, трехгодовалый сын и ихний сосед напротив


DayGaykin ©   (02.06.17 00:14[10]


> Тимохов Дима ©   (01.06.17 21:31) [7]

Ты угадал, речь идёт о мифических телах 👩 В моем случае вес от 25 до 90 единиц.

Класть яблоки зигзагом не лучшая затея. Очевидно, что достаточно просто может получиться несправедливо:) пока я также отсортировал и каждое следующее кладу в самую лёгкую корзину.
Получается достаточно равномерно, но сорта в перемешав все.


картман ©   (02.06.17 01:08[11]

Это управленческая задача.

Каждому носильщику кладешь в корзину все яблоки одного сорта. Убеждаешь в том, что доставшийся ему сорт - лучший. Все довольны.


rrrrr ©   (02.06.17 08:29[12]

погромист всегда решает свою задачу, а не ту которая поставлена.


Inovet ©   (02.06.17 10:06[13]

> [7] Тимохов Дима ©   (01.06.17 21:31)
> 4. И т.д. - чередуем в прямом порядке и в обратном порядке.

И получаем бесконечный цикл при некоторых условиях.


rrrrr ©   (02.06.17 10:13[14]

а с чего вы все взяли, что надо разделить все яблоки поровну по всем корзинам?
если бы требовалось это, в задаче так бы и было сказано.
"поделить поровну m яблок на n корзин"


Тимохов Дима ©   (02.06.17 13:25[15]


> Inovet ©   (02.06.17 10:06) [13]
> > [7] Тимохов Дима ©   (01.06.17 21:31)
> > 4. И т.д. - чередуем в прямом порядке и в обратном порядке.
> И получаем бесконечный цикл при некоторых условиях.

Почему? Берем яблоки по порядку возрастания. Они когда-то кончатся)))

> DayGaykin ©   (02.06.17 00:14) [10]
>
> > Тимохов Дима ©   (01.06.17 21:31) [7]
>
> Ты угадал, речь идёт о мифических телах 👩 В моем случае
> вес от 25 до 90 единиц.
>
> Класть яблоки зигзагом не лучшая затея. Очевидно, что достаточно
> просто может получиться несправедливо:) пока я также отсортировал
> и каждое следующее кладу в самую лёгкую корзину.
> Получается достаточно равномерно, но сорта в перемешав все.


Думаю, что если провести численный опыт примерно на реальных данных: 100-200 корзин, и по 20-40 яблыков в каждой, то среднее отклонение будет примерно одинаков в твоем и моем случае. Будет кураж и время, попробую.)


manaka ©   (02.06.17 13:51[16]


> Есть N корзин и M яблок.


Решение 1.
Каждое яблоко режем на N равных частей и кладем по одной части в каждую корзину.
У всех поровну и по весу и по сортам.

Решение 2.

> 1. Какой критерий можно считать самым справедливым?

Отсюда  Решение 3, Решение 4, ..., Решение К


Тимохов Дима ©   (02.06.17 13:59[17]


> Решение 1.
> Каждое яблоко режем на N равных частей и кладем по одной
> части в каждую корзину.
> У всех поровну и по весу и по сортам.


Еще решение: яблоки перемалываем мясорубкой в пюре. И его разливаем по корзинам.
Полагаю, что самым довольным будет тот, кому не хватит пюре - на голову ничего литься не будет...


manaka ©   (02.06.17 14:08[18]

Все яблоки в одну корзину и нести по очереди.


Inovet ©   (02.06.17 15:42[19]

> [15] Тимохов Дима ©   (02.06.17 13:25)
> Они когда-то кончатся)))

Ага. это я про одинаковые видимо подумал.


версия для печати

Написать ответ

Ваше имя (регистрация  E-mail 







Разрешается использование тегов форматирования текста:
<b>жирный</b> <i>наклонный</i> <u>подчеркнутый</u>,
а для выделения текста программ, используйте <code> ... </code>
и не забывайте закрывать теги! </b></i></u></code> :)


Наверх

  Рейтинг@Mail.ru     Титульная страница Поиск, карта сайта Написать письмо