给定多个选项,我需要选择其中的 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);
我已经尝试了几个不同的选项,循环内循环的所有变体。 但当然,它们的执行速度非常缓慢,或者根本不会返回。
我认为仅仅循环是行不通的,必须有一个 解决这个问题的根本不同的方法。
最佳答案
这正是 knapsack problem ,即 NP-Complete - 所以没有已知的多项式解。
但是,如果您的权重(成本)是相对较小的整数,则有一个非常有效的 pseudo-polynomial solution using dynamic programming .
关于javascript - 如何优化搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18146111/