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.

In reply to Re: Challenge: Twist On Bin Packing by moklevat
in thread Challenge: Twist On Bin Packing by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.