How to optimise search

Question

Given multiple options, I need to select n of them, such that the total rating is maximized, but the total cost does not exceed the budget.

var options = [
    { rating: 8, cost: 6, },
    { rating: 5, cost: 4, },
    //...100 of these in total
];

function select(n, budget) {
    //TODO: Replace this code with some real implementation
    return options.slice(0, 5);
}

//Sudocode:
var result = select(5, 25);
Assert(result.length == 5);
Assert(sum(result.cost) <= 25);
Assert(sum(result.rating) is maximized);

I have tried a few different options, all variations of loops inside loops. But of course, they perform very slowly or never return at all.

I think that just looping is never going to work, and that there must be a fundamentally different approach to this problem.

Answer 1

This is exactly the knapsack problem, which is NP-Complete - so there is no known polynomial solution to it.

However, if your weights (costs) are relatively small integers, there is a pretty efficient pseudo-polynomial solution using dynamic programming.