NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

## All the Perl that's Practical to Extract and Report

#### gav (2710)

gav
(email not shown publicly)
http://www.estey.com/
AOL IM: flufflegavin (Add Buddy, Send Message)

Hacker in NYC.

### Journal of gav (2710)

Friday September 05, 2003
08:50 AM

### algorithms

[ #14508 ]

Given a set of integers, is there an easy way to find the highest combination that is less than or equal to a maximum?

For example given (3, 7, 5) and a target of 13 we'd want 7+3+3=13 (though 5+5+3 is also correct, we only need one solution). If we had (4, 6, 12) and a target of 7 the maximum would be 6.

I can't seem to work out a "nice" algorithm to handle this, is there anything obvious I'm missing?

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Full
Abbreviated
Hidden
• #### First Glance(Score:1)

This appears to be the packing problem. (Or am I missing something?)

No perfect way to solve it. Lots of imperfect solutions abound, and there's probably one that suits your needs somewhere out there...

--

------------------------------
You are what you think.
• #### Re:First Glance(Score:2)

In the packing problem you can use each member of the set at most once. In this problem you can use a member multiple times. That probably doesn't make it easier, though.
• #### Re:First Glance(Score:1)

In the packing problem you can use each member of the set at most once. In this problem you can use a member multiple times. That probably doesn't make it easier, though.

Indeed, it doesn't. Actually it makes it harder. :-) Now you suddenly have no longer simple permutations but instead much more possibilities to combine numbers together.
• #### Re:First Glance(Score:1)

Ahh. Another lesson to myself in the dangers of taking a single glance and moving from there...
--

------------------------------
You are what you think.