Задача по набору предметов с условием. Каков алгоритм решения?

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

upd: Прошу прощения. Метод ветвей и границ всё таки является точным решением.