Smallest to largest won't always give the maximum number of bins. Take 1,1,1,2,2,3,4,6,7,7 for example.
Filling them smalles to largest you get 4 bins:
1,1,1,2,2,3
4,6
7
7
But you can get 5 bins by filling it:
6,1,1,1
2,2,3
7
7
4
| [reply] |
Well, crap. You should un-anonymize yourself so I know who to hatethank.
| [reply] |
Ack! Neat! Can you describe the algorithm?
| [reply] |
No, I'm still trying to work one out :)
I figured if the smallest to largest wasn't going to work, it would likely be due to combinations of numbers where the smaller numbers add up to 10, but using larger numbers add up to 9.
A little trial and error found it.
I'm kinda thinking about something along the lines of "Use all the 1s to add up to 10, use all the 2s to add up 9, use all the 3s to add up 8, etc.", but I haven't been able to determine whether that is always going to work or not.
| [reply] |
It seems that L~R has some work cut out to compare the Least-to-Greatest method with any other contenders, on a large enough set of random samples, and tell us if there are any interesting anomalies. [Well, it is his problem, and I have to get some work done before home-time ;]
-QM
--
Quantum Mechanics: The dreams stuff is made of
| [reply]
[d/l] |
This is cool. The least-to-greatest approach will indeed give a larger number of bins than the approach I posted above under some circumstances, so this may be the winner. However, it will also lead to larger variability in the contents of the bins and could lead to more bins being, for example, 51% full. Ultimately the relative importance of "filling the bins as close to capacity as possible" and "maximizing the number of bins" remains somewhat unclear. | [reply] |
