CODEWITHSUNDEEP
algorithmmath
pranay
pranay

Reputation: 2369

selecting an integers to maximise sum

if we are given pairs of integers (a1,b1),(a2,b2),(a3,b3),..(an,bn) and there is a maximum sum value = X then how can we select the given pairs such that sum of the first entries (i.e. a1, a2,..ap)amongst the selected pairs is maximum but <= X ? E.g if the given pairs are (43,9),(57,12),(13,4) and maximum sum is 71 then the pairs we can select are (57,12) and (13,4) giving a maximum sum <=71(X) as 70 . My initial approach is to sort the pairs based on first entry values in descending order and then maybe an O(n^2) algorithm ..but am not sure about this and it also may be too slow for large amount of data..So is there any efficient approach to it? Thanks.

Upvotes: 0

Views: 135

Answers (1)

smang
smang

Reputation: 1207

Sounds like this could be implemented with a modification of the 0-1 Knapsack problem.

Upvotes: 1

Related Questions