如何优化search

给定多个选项，我需要select其中的n个，以使得总评价最大化，但总成本不超过预算。

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); 

我已经尝试了几个不同的选项，循环内循环的所有变化。 但是，当然，他们performance得非常缓慢或根本不会回来。

我认为循环是永远不会起作用的，对这个问题必须有一个根本不同的方法。

Answer 1

这正是背包问题 ，这是NP完全的 – 所以没有已知的多项式解决scheme。

然而，如果你的权重（成本）是相对较小的整数，那么使用dynamic规划是一个相当有效的伪多项式解决scheme 。