Given a total and an array of integers what is the best algorithm to find the subset of integers whose sum is equal or closest to the total?

Asked Feb 03 '16 at 09:11

Active Feb 24 '19 at 13:33

Viewed 42 times

Given a total and an array of integers what is the best algorithm to find the subset of integers whose sum is equal or closest to the total? Subset sum problem only tells whether it's possible to achieve the total or not . In this problem in case that fails I have to calculate the subset whose sum is closest to the total?

For example

Given total =100 
And integers as  { 20,30,40,55 } 
The Correct answer should be 95 {40+55}

Is there an algorithm to calculate this?

edited Feb 24 '19 at 13:33

Cœur

37,241
25
195
267

asked Feb 03 '16 at 09:11

Aman Kumar Sinha

Do you really believe that nobody asked about 'subset sum' here? – MBo Feb 03 '16 at 09:22
The dynamic programming solution to the subset sum problem will solve this problem as well. – pseudoDust Feb 03 '16 at 11:24

Given a total and an array of integers what is the best algorithm to find the subset of integers whose sum is equal or closest to the total?

0 Answers0