I’m trying to write an algorithm that, given a number of credits and a set of objects that have different values, calculates: 1) The smallest set of objects which values add up to the number of credits.
2) if 1 is impossible (no combination adds up to the number of credits) finds the set of objects that comes closest to the amount of credits (the sum must be strictly less than the amount of credits). If more than one set adds up to the same number of credits the smallest set should be returned.
By smallest set I mean the set with the least objects.
In english: I'm trying to pay a price with the smallest amount of objects possible. If that cant be achieved I want to pay the closest to such amount possible (less than) with the smallest amount of objects.
credits: 6 objects: 10 5 2 2 2 Result: 2 2 2
credits: 10 objects: 5 2 11 2 1 5 Result: 5 5
credits: 9 objects: 5 2 10 Result: 5 2
I was wondering if there is any algorithm already developed to do such a search.