Задача такова - есть группа алмазодобытчиков, три человека. Они могут найти несколько алмазов (до 20 допустим), каждый стоит определенную цену. Вопрос таков - как им точно разделить эти алмазы по цене? пример: нашли 5 алмазов, стоят: 1,1,1,1,2, ответ: разделить можно, а такой пример: нашли 6 алмазов, стоят: 12 13 14 100 100 100 ответ: разделить нельзя. 
8 алмазов 25 13 5 5 5 6 12 4 разделить можно. 
С чего бы вы начали? Может есть такой алгоритм и он как-то называется замудрено? 

Сорри, опечатался, перепутал цены.

Это сообщение отредактировал(а) jezismaria - 1.5.2011, 15:19

Что-то ничего кроме метода Монте-Карло в голову не лезет.

.................................
Если же практически, то алмазы прекрасно делятся на того из старателей, кто лучше стреляет  

Тут цифр больше 6-и, как же они их разделят?
Получается, что нельзя разделить, когда цифр больше чем алмазов. Вот и весь алгоритм.

nworm, идея непонятна. Цифр-то всегда 10. Вряд-ли старатели знакомы с шестнадцатеричной системой счисления.  

Почему, отличная идея, по-моему, в первом случае 5 цифр, во втором целых 11. 

_Y_, а как 10 то получилось? Метода Монте-Карло задействован?

Методом полного перепора, эта задача класса НП.

Въехал! Это ты количество алмазов "количеством цифр" называешь. Странно, ну да ладно.

Скажем 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
Получилось число дробное - значит поделить честно нельзя. 


Если бы получилось число целое, можно было бы переходить к поиску комбинаций укладки алмазов в три кучки. Критерий: сумма коэффициентов стоимости алмазов в каждой кучке должна быть равна числу, полученному в результате предидущего рассчета.

Если алмазов не очень много - можно перебрать все варианты. А если очень - тогда как-то еще.

Это сообщение отредактировал(а) _Y_ - 1.5.2011, 20:29

То тогда генным алгоритмом 

Добавлено через 1 минуту и 26 секунд
Кстати похожие задачи (например распределение определенной суммы денег по разным банкам) решаются именно генетическим алгоритмом. Может стоит попробовать?

Bitter, я подумал сначала про генетические алгоритмы, но не смог вообразить как положить такую задачу на хромосому. Опиши, пожалуйста. Интересно  

Задача принадлежит классу НП, ее решение экспоненциальные перебор.

В чем смысл генетических алгоритмов тут?