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 完全なナップザック問題です。そのため、既知の多項式解はありません。

ただし、重み (コスト) が比較的小さい整数である場合は、動的計画法を使用した非常に効率的な疑似多項式ソリューションがあります。

于 2013-08-09T12:06:54.723 に答える