алгоритм для нахождения лучшей комбинации

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

Это в Целочисленном Линейном Программировании, оптимизируя линейное уравнение, подвергающееся линейным ограничениям, где все переменные и коэффициенты являются целыми числами.

Вы хотите переменные includeItem1..., includeItemN с ограничениями 0  includeItemi  1 для всех значений меня и includeItem1 +... + includeItemN ≤ 15 и includeItem1*priceItem1 +... ≤ 10, максимизируя includeItem1*kilojouleItem1 +....

Палка, что в Вашем любимом целочисленном линейном решателе программы и получают решение :)

См. также http://en.wikipedia.org/wiki/Linear_programming

Не имеет смысла говорить, что Ваша конкретная проблема полна NP, но это - экземпляр полного NP (отчасти) проблема, таким образом, не могло бы быть теоретически быстрого способа сделать его. В зависимости от того, как близко к оптимальности Вы хотите добраться и как быстро работа решателей ILP, это могло бы быть выполнимо на практике.

Я не думаю Вы, проблемой является особый случай ILP, который делает особенно легким решить. Просматривая его как подобную ранцу проблему, Вы могли ограничить себя рассмотрением всех подмножеств 1.. 100, которые имеют самое большее (или точно) 15 элементов, который является многочленом в n---, это - n-choose-15, который является меньше, чем (n^15) / (15!), но это не ужасно полезно когда n = 100.

Если Вы хотите рекомендации для программ решателя, я попробовал glpk и нашел приятным использовать. В случае, если Вы хотите что-то, что стоит денег, мой лектор всегда говорил о CPLEX как пример.

Это больше походит на линейную проблему программирования.

Неофициально, линейное программирование определяет способ достигнуть лучшего результата (такого как максимальная прибыль или самая низкая цена) в данной математической модели и, учитывая некоторый список требований, представленных как линейные уравнения.

Проверьте Симплекс-метод.

Это - задача о ранце, если можно или выбрать продукт или нет. Если можно выбрать дробные значения продуктов затем, Вы могли бы решить это с симплекс-методом, но дробная задача о ранце имеет простое решение.

Закажите объекты отношением энергии/цены, выбрав 100% самых высоких, пока Вы не остаетесь без денег, затем выберите дробное значение самого высокого оставления тем.

Например, если цены 4,3,5,4, и энергии 3,5,2,7, упорядочивание

7/4, 5/3, 3/4, 2/5

Таким образом, Вы выбрали бы объекты 4 и 2, который будет стоить 7$, с оставлением за 3$ Вами купил бы 75% первого объекта за цену 3$ и энергию 3*.75 = 2.25

Это дало бы полную энергию 14,25

Обратите внимание, что разрешение дробных значений даст Вам более высокое объективное значение, чем только разрешение 0% или 100%, таким образом, никакое целочисленное решение не сделает немного лучше, чем 14,25 (или 14 в этом отношении, так как объективное значение должно быть целым числом).

Для решения исходной задачи о ранце можно использовать метод ветвей и границ, который должен работать просто великолепно на практике. Предположите, что у Вас есть текущий вариант решения с объективным значением z*

1. Решите расслабленную проблему, где Вы позволяете дробные веса. Если значение является меньше, чем z*, отбросьте это ответвление.
2. Вычислите новое значение z, который является решением, найденным без последнего дробного веса, если это значение больше, чем z*, замена z* с Вашим новым значением
3. Выберите один объект (скажите, что первое в списке, самом прибыльном), и формируют две подпроблемы, тот, где необходимо включать его в решение и то, где Вы не можете включать его в решение (это - переходящий шаг).
4. Пока Вы имеете подпроблемы в запасе для решения, выберите один и вернитесь к шагу 1.

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

Поскольку более подробное описание смотрит на Ответвление и Привязанный Википедия.

Каменные реализации Списков хранилищ Алгоритма Ручья для задачи о ранце.

Их книга Руководство по проектированию Алгоритма имеет этот вид информации для обширного массива проблем.

Это напоминает мне об известном алгоритме ранца

http://en.wikipedia.org/wiki/Knapsack_problem

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

SELECT TOP 15 *
FROM Product
WHERE Price < 10
ORDER BY Energy DESC

Должно быть возможно решить проблему со Сливками для Java. Существует также версия для доступного CSharpCream C#.