8 алмазов 25 13 5 5 5 6 12 4 разделить можно.
С чего бы вы начали? Может есть такой алгоритм и он как-то называется замудрено?
Сорри, опечатался, перепутал цены.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Помогите найти алгоритм решения задачи |
| Автор: jezismaria 30.4.2011, 22:05 |
| Задача такова - есть группа алмазодобытчиков, три человека. Они могут найти несколько алмазов (до 20 допустим), каждый стоит определенную цену. Вопрос таков - как им точно разделить эти алмазы по цене? пример: нашли 5 алмазов, стоят: 1,1,1,1,2, ответ: разделить можно, а такой пример: нашли 6 алмазов, стоят: 12 13 14 100 100 100 ответ: разделить нельзя. 8 алмазов 25 13 5 5 5 6 12 4 разделить можно. С чего бы вы начали? Может есть такой алгоритм и он как-то называется замудрено? Сорри, опечатался, перепутал цены. |
| Автор: _Y_ 30.4.2011, 22:43 |
| Что-то ничего кроме метода Монте-Карло в голову не лезет. ................................. Если же практически, то алмазы прекрасно делятся на того из старателей, кто лучше стреляет  |
| Автор: nworm 30.4.2011, 23:03 | ||
Тут цифр больше 6-и, как же они их разделят? Получается, что нельзя разделить, когда цифр больше чем алмазов. Вот и весь алгоритм. |
| Автор: _Y_ 1.5.2011, 10:55 |
nworm, идея непонятна. Цифр-то всегда 10. Вряд-ли старатели знакомы с шестнадцатеричной системой счисления.  |
| Автор: nworm 1.5.2011, 12:44 |
| Почему, отличная идея, по-моему, в первом случае 5 цифр, во втором целых 11. _Y_, а как 10 то получилось? Метода Монте-Карло задействован? |
| Автор: esperanto 1.5.2011, 19:19 |
| Методом полного перепора, эта задача класса НП. |
| Автор: _Y_ 1.5.2011, 20:28 | ||||
Въехал! Это ты количество алмазов "количеством цифр" называешь. Странно, ну да ладно. Скажем 11 алмазов (даже и простое число) надо разделить на 3 старателей (да еще и по-честному). По-твоему получается, что это невозможно. Но алмазы-то стОят, например: 5 4 4 4 2 2 2 2 2 2 1 Делим алмазы между персонажами: 5+4+1=10 4+4+2=10 2+2+2+2+2+2=10 Все по-честному получилось.  Другое дело, что не из каждого набора такое можно сделать.Добавлено через 12 минут и 26 секунд jezismaria, я вот подумал. До того как мучить метод Монте-Карло, можно осуществить простую проверку: 1. Делим стОимость каждого алмаза на наибольший общий делитель. Ну например, если есть набор алмазов стоимостью 45 60 300, то делим на 15 и получаем коэффициенты 3 4 20 2. Суммируем коэффициенты стоимости всех алмазов 3+4+20=26 3. Делим на число старателей 26/3=8,666666 Получилось число дробное - значит поделить честно нельзя. Если бы получилось число целое, можно было бы переходить к поиску комбинаций укладки алмазов в три кучки. Критерий: сумма коэффициентов стоимости алмазов в каждой кучке должна быть равна числу, полученному в результате предидущего рассчета. Если алмазов не очень много - можно перебрать все варианты. А если очень - тогда как-то еще. |
| Автор: Bitter 1.5.2011, 23:59 | ||
То тогда генным алгоритмом Добавлено через 1 минуту и 26 секунд Кстати похожие задачи (например распределение определенной суммы денег по разным банкам) решаются именно генетическим алгоритмом. Может стоит попробовать? |
| Автор: _Y_ 2.5.2011, 12:04 |
| Bitter, я подумал сначала про генетические алгоритмы, но не смог вообразить как положить такую задачу на хромосому. Опиши, пожалуйста. Интересно |
| Автор: esperanto 2.5.2011, 21:11 | ||
Задача принадлежит классу НП, ее решение экспоненциальные перебор. В чем смысл генетических алгоритмов тут? |
