Stories
Slash Boxes
Comments
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

use Perl Log In

Log In

[ Create a new account ]

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?


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

algorithms 4 Comments More | Login | Reply /

 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • 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.
    • 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.
      • 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.
      • Ahh. Another lesson to myself in the dangers of taking a single glance and moving from there...
        --

        ------------------------------
        You are what you think.
Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.