3

给定多个选项,我需要选择其中的 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);

我尝试了几个不同的选项,循环内循环的所有变体。但是,当然,它们的执行速度非常缓慢,或者根本不会返回。

我认为仅仅循环是行不通的,必须有一种根本不同的方法来解决这个问题。

4

1 回答 1

3

这正是背包问题,它是NP-Complete - 所以没有已知的多项式解决方案。

但是,如果您的权重(成本)是相对较小的整数,则使用动态规划有一个非常有效的伪多项式解决方案

于 2013-08-09T12:06:54.723 回答