Coding Help - Sort Into Least Number of Groups

[tesco]

This is a good one for any coding experts that are here (if we have any )...
I need this in PHP but I don't need you to write the code, I just need the logic of how this will work then I could probably write it myself.

Lets say I have an array of values like so...

10, 56, 78, 25, 18, 1, 8

I want to group these together so that each group is less than or equal to 100, with the least number of groups possible.

Well this is what the groups would be in an efficient sorting:
Group 1 = 10, 56, 25, 1, 8
Group 2 = 78, 18

There are other combinations of course, but the point is that we have 2 groups.

If I were to just simply loop through them and add the values, and start a new group when i reach the max (100), that will result in this:
Group 1 = 10, 56
Group 2 = 78
Group 3 = 25, 18, 1, 8

Or if I were to sort them, then loop through them like above, this would be the result:
1, 8, 10, 18, 25, 56, 78
Group 1 = 1, 8, 10, 18, 25
Group 2 = 56
Group 3 = 78

So now hopefully you see what the problem is...

What is the logic behind this that I could sort them like my "efficient sorting" example?

[Slickerey]

I had to reread this post about three times before I could understand what you're trying to say.

I understand what you're trying to say, but writing down the code to ensure that PHP will know how to organize the groups might take some time. I don't know if a foreach() function would help, but testing and trying wouldn't hurt.

[tesco]

I explained the best I could by giving 3 examples.

edit: Just noticed that if I sort the values reverse then Loop through and pick out whatever ones I can fit, starting from the highest, it seems to work out.

For example with teh above numbers:
78, 56, 25, 18, 10, 8, 1
Group 1 = 78 18 1
Group 2 = 56 25 10 8

Or with some new numbers:
76 74 65 65 43 34 25 23 23 21 12 12 1
Group 1 = 76 23 1
Group 2 = 74 25
Group 3 = 65 34
Group 4 = 65 23 12
Group 5 = 43 21 12



Guess I just figured this out myself. I thought it would have been more complicated...

[Expeto]

What an interesting problem, but since my php coding skills are , at best, I will take a mathematical approach. I wrote a similar code for my calculator some time ago, this is how it worked :

sort() the original array of numbers, low to high. => 1 12 12 21 23 23 25 34 43 65 65 74 76

$n=1
$m= number of the items in the array
         if [ "$nth number" + "$mth number" < 100 ]
           then
                       "$nth number" + "$mth number" = $x
                       $n + 1 = $n
                       while [ $x + $nth number < 100 ]
                                             x + $nth number = $x
                                             $n + 1 = $n
                       done
                       store $mth and the numbers lower than $n as an array
                       $m - 1 = $m
           else
                     store $mth number alone as an array
                     $m - 1 = $m
           fi

I'm pretty sure there is a better way to do this. I actually used few other wrongs ways in my real code. For example one of them just added first and last numbers and store them as arrays, another added random items to find 90+ arrays groups than it looked for 80+, 70+ and 50+ arrays from remaining numbers. In mine there was also a final part to decide the result generated by which way was the best and a logger to note which way was used. I was planning to connect this to a random number generator and inspect the logs to find which was most effective But my calculator got stolen and I forgot the project.

Please let me know if you find a better way