검색을 최적화하는 방법

Question

여러 옵션이 주어진 경우 총계가 최대가되도록 이 예산을 초과하지 않도록 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); 

몇 가지 다른 옵션을 시도해 보았습니다. 루프 내부의 루프가 모두 유사했습니다. 물론 그들은 매우 천천히 수행하거나 전혀 돌아 오지 않습니다.

저는 루핑이 절대로 작동하지 않을 것이며,이 문제에 근본적으로 다른 접근 방식이 있어야한다고 생각합니다.

Answer 1

정확히 knapsack problem입니다. 이는 NP-Complete이므로 알려진 다항식 솔루션이 없습니다.

그러나 가중치 (비용)가 비교적 작은 정수인 경우에는 pseudo-polynomial solution using dynamic programming이 매우 효율적입니다.