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

Question

[Agiot]

Дано: N (100) предметов. У каждого свои стоимость и вес. Стоимость и вес не зависят друг от друга. Есть ограниченный бюджет. Нужно из этих предметов выбрать строго n (5) предметов, чтобы их суммарная стоимость не выходила за рамки бюджета и их суммарный вес был максимален. Можно задачу решить перебором, но этот метод затратен по времени, поэтому не годится. Помогите, пожалуйста, решить задачу.

Answer 1

[Lander]

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

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