Всем доброго времени суток!

Задача следующая: 
Есть множество P каждый элемент которого имеет некоторую цену pi; и есть заданная цена W. 
Необходимо выбрать элементы из P так, чтобы количество элементов было минимальным, а сумма цен элементов была больше или равна W. Если вариантов несколько, выбрать тот, который ближе к W.

Например, 
элементы [100, 20, 30, 50], цена 100, нужно выбрать [100]
элементы [100, 30, 20, 50, 10], цена 80, нужно выбрать [50, 30]
элементы [100, 30, 20, 50, 10], цена 85, нужно выбрать [50, 30, 10]

Теорию оптимизации совсем не помню, поэтому буду признателен любой наводке.

Добавлено через 2 минуты и 18 секунд
Да, кстати, числа могут быть довольно большими (в пределах long)

Вот что придумалось

поиск (P, W, результат)

•  Если P пустой и W > 0, возвращаем пустой список
•  Если P пустой и W < 0, возвращаем результат
•  P не пустой. Есть два варианта - поместить первый элемент из P в результат или не поместить
•  помещаем p0 в результат: with <- поиск(tail(P), W - head(P), head(P) ++ результат)
•  не помещаем p0 в результат: without <- поиск(tail(P), W, результат)
•  если сумма в with больше W, а сумма в without меньше, возвращем with
•  если сумма в with меньше W, а сумма в without больше, возвращем without 
•  если сумма в with меньше W, и сумма в without меньше, возвращем пустой список
•  если сумма в with ближе к W, возвращаем with, иначе without
•  если сумма одинаковая, а количество элементов в with меньше, возвращаем with, иначе without

Перед этим еще можно сразу же выкинуть все элементы из P, которые больше W и заодно проверить, есть ли в P такой pi что pi == W
Чем-то напомнинает рюкзак. Что скажете?

Это сообщение отредактировал(а) Stolzen - 10.8.2012, 15:20

Вывод из формулировки - количество приоритетнее близости суммы. Следовательно, во 2 и 3 вариантах следует выбрать то же решение, что и в первом варианте - именно это решение даёт минимальное количество элементов.


Прежде чем формулировать задачу остальным, следует её до конца осмыслить для себя.

Да, не совсем верно сформулировал, близость к сумме конечно приоритетнее, чем количество элементов. 

Думаю так должно работать быстрее:



Это сообщение отредактировал(а) korian - 13.8.2012, 17:35

korian, спасибо. А можно на словах описать, что тут происходит? 
У меня вот такая реализация для алгоритма выше получилась.

Всё равно не до конца понятно. Как они соотносятся? если нужна сумма 98, она не набирается, а набирается 99 из 11 элементов или 100 одним элементом - какой вариант выбрать?
Где математическое определение критерия оптимальности?

У меня нет такого, извините.


Склоняюсь к 99.

Меня, по правде, больше интересовали подходы к решению подобных задач. Спасибо.

Я добавил комментарии.


Мне тяжело читать функциональные языки %)
Можете проверить ваш алгоритм на таких данных (я их использовал для своих тестов и это вроде как основные моменты, которые надо проверить):


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


Это сообщение отредактировал(а) korian - 13.8.2012, 17:11

Ну здесь Вы собсно имеете в чистом виде задачу об одномерном раскрое. И решаете её соответственно. Либо какой-то точный переборный метод, скажем метод ветвей и границ, либо (если устраивает решение, близкое к оптимуму, а необязательно оптимум) генетика.


А вот это очень плохо. Вы обязаны иметь... ммм... ну, скажем, функцию, в которую Вы передаёте два решения, а она возвращает ответ, какое из них лучше. Иначе решать задачу не получится. Ощущения класса "склоняюсь к" не программируются.

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


Дело в том, что мы пока в команде сами не знаем, какие именно критерии выбора решения лучше использовать, поэтому перебираем разные варианты и смотрим, какой из них лучше ведет себя для тестового набора данных. Ну и в данном случае ведь выбор ответа - это дело одной-двух проверок, поэтому можно сначала проверить ощущения типа "склоняюсь к", а потом другие   


Спасибо, нашел пару опечаток и неточностей в коде. (Вот новая версия.)


Да, теперь немного понятнее. Получается, примерно такая же идея, как в посте 2, только алгоритм реализован эффективнее? У этого алгоритма есть какое-нибудь название?

Заодно почитай и задачу о рюкзаке (вариация - об одномерном рюкзаке). Она отличается от раскроя тем, что в ней есть относительные веса/стоимости, о чём обычно забывают, благополучно путая меж собой эти задачи.

В общем да. Эффективнее тем, что я на каждом шаге уменьшаю размер множества, если это возможно. Т.е. рассматриваю подмножество элементов, в котором только элементы, которые меньше W, плюс один наименьший элемент, который больше W. Ну и учитывая, что множество отсортированное, это стоит мне всего log(n) времени.
Плюс если я правильно понимаю, моему алгоритму надо меньше времени для определения, что сумма множества меньше W.


Без понятия, особо этим не интересовался. Написан за субботу от нечего делать.


Это сообщение отредактировал(а) korian - 14.8.2012, 17:03

korian, Akina, спасибо вам за отклик, на пока тему можно считать закрытой.