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.

---

---

• 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.