subset which gives the least sum greater than or equal to a given number

Viewed 1463

I have a (multi)set of positive numbers, eg. {71.28, 82.62, 148.77, 85.05, 50.76, 103.41}.

I want to find the subset which gives the least sum greater than or equal to a given number.

Eg. if the minimum was 270, then the result would be {148.77, 71.28, 50.76}, which sums to 270.81.

Note: I assume the solution might be more similar to knapsack than subset sum.

1 Answers
Related