Very interesting. In thinking about this it might be easier to find a solution if the problem is slightly refactored. Rather than discussing bins and gifts, I think that this problem lends itself better to considering volumes of liquid. We are not concerned with the way in which our bins are packed, rather we assume that whatever unit volume we place in each bin automatically fits in the best possible way (like liquid). Since we can consider this a problem of liquids, we may as well discuss beer. :-)

I therefore propose the following modification of the problem as the The Pint Pouring Problem

At your local pub all beer is served in 1 pint glasses. Following a serious problem at the brewery today's shipment of beer was delivered in cans of various sizes, each less than a pint. The thrifty pub owner asks you to devise an algorithm for pouring as many pints as possible, but that also ensures that as many patrons as possible get a suitably full pint glass (say at least 90% full). Assume that cans cannot be split across pint glasses. Fewer pints poured means less revenue for the pub owner, but inadequately filled pints mean angry patrons and the potential for trouble.

Now to work on a solution...

Update:The combination of "as full as possible" and "as many bins as possible" in the original post create an inherent conflict (which, I suppose, is the point). Having said that, I have not been able to think of a case for which a variation on the "Best Fit Decreasing and First Fit Decreasing" strategy will fail. (that's not to say there isn't one, but I have to get *some* work done today).

The algorithm:

0) Step zero is to set a threshold for adequately "full" that is less than 100%.

1) Sort all cans by size.

2) Begining with the largest can and moving smaller, pour as many cans in order that will fit in a single glass. If you come to a can that will overflow the glass go to the next step.

3) Beginning with the smallest cans and moving larger pour as many cans in order that will fit in the glass. If you come to a can that will overflow the glass go to Step 2 and begin filling the next glass.

Update:I have removed step zero. Limbic~Region didn't like it and it is unnecessary. It simply reparameterized the problem as if you had smaller glasses.

Final Update:The problem has been clarified somewhat and this solution does not fit, as L~R notes below.

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.