Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

simple examples:

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.

share|improve this question
    
If you add the constraint that the value of each object you have to use (barring duplicates) is always at least double the next smallest item, you can use a greedy algorithm. If not, you can't. (Which is why solving this problem with "real money" is easy and fast, and also why that property is exhibited in all countries currency.) –  Servy Sep 4 '13 at 21:09
4  
This appears to be a variation on the knapsack or subset sum problem. Both of these have well researched algorithms for solutions (and both are NP). –  MichaelT Sep 4 '13 at 21:20
2  
They are NP-complete, not just NP. The greedy variant is NP just as well, simply because P is contained in NP anyways. –  Frank Sep 5 '13 at 5:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.