1
$\begingroup$

I have a list of pairs with values and costs:

    | value | cost |       
    11, 1000    
    7, 700
    7, 700
    6, 700
    2, 400
    2, 500
    1, 600

The list is ordered by value/cost decreasingly. The task is, given a budget X find the maximum value you can get while keeping the total cost within the budget. In the sample example, if X=1400, the maximum value would be 14.

What algorithm would be the most efficient to find this value?

$\endgroup$
  • 1
    $\begingroup$ Your problem is known as KNAPSACK. It is NP-hard. $\endgroup$ – Yuval Filmus Sep 8 at 13:19
  • $\begingroup$ That is unfortunate, although I will only deal with small n, so it won't be too much of a bottleneck. Thanks for the info! $\endgroup$ – schapke Sep 8 at 14:02
0
$\begingroup$

Your problem is KNAPSACK, one of the classic NP-complete problems. Wikipedia contains a wealth of information about the problem, include exact and approximation algorithms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.