First, lets order the bins 1 through N. I'll call a packing 1-stable if no set of single elements can be moved from later bins B to earlier bins A to reduce the muber of bins used. In this sense the OP solution is is 1-stable: the 2 cannot be moved to an earleir bin.

If there is no ordering requirement, the OP soultion is not stable: I can move the 5 and the 2 to the fourth bin, the 3 to the first bin and the 4 to the third bin to eliminate a bin. So, the OP must be thinking about the ordered case.

Simialrly, suppose 2-stable allows both sinlge moves and transpositions. Then the 2 and 3 of the first and third bins can be excahnged and then 2 in the fourth bin can be moved into the third bin, reducing the number of bins. So the OP must be only thinking about single moves.

To solve the ordered 1-stable problem, I suggest, sorting the gifts from smallest to largest and then fill up bins using sequential elements from the sorted list. For the OP example, (2, 2, 3, 4, 5, 6, 7) this would give 

    1: 2,2,3
    2: 4,5
    3: 6
    4: 7

[download]
which gives the same maximum number of bins, but spreads the gifts about more evenly. Intuitively, by using up all the smallest elements that could be used to fill up the interstices first, the remaining bins will be taken up by larger elements with lots of empty space.

-Mark

In reply to Re: Challenge: Twist On Bin Packing by kvale
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.