I want to find an example of where a non-greedy method of partitioning numbers is better than the greedy method. The greedy method would be to partition them so that you group as many numbers as possible with their sum being less than or equal to the threshold.
e.g. greedy method : 11 + 1| 9 + 2 + 2 | 3 + 5 where the threshold is 13
non greedy method: 11 | 1 + 9 + 2 | 2 + 3 + 5
I am trying to think of an example where the non-greedy method would use less partitions than the greedy method. Please help!
The problem you refer to is called bin packing, and it's been extensively studied for its great practical importance. In fact, bin packing was the first problem for which the issue of "greedy vs. non-greedy" was studied. The standard terminology for it is "online vs. offline": informally, online algorithms are ones that "accomodate" the input as it arrives, instead of waiting until they know it all to make their decisions. A crucial measure of the quality of an online algorithm is its competitive ratio: roughly speaking, the worst case ratio between the cost it incurs (for bin packing, the number of bins) and the lowest cost one could possibly incur, as the latter tends to infinity.
For bin packing, the lower bound on the competitive ratio is known to be more than 1.54; and there are complicated online algorithms that manage a competitive ratio below 1.58. I'd note that it's significantly easier to manage a competitive ratio of 1.6, and very very, easy to manage 2.