BrowserUk,
Regarding #2 (sorting the input), this is also a bust. You have to sort in descending order for my original edge case to work but if you sort in descending order for the following test case it doesn't produce optimal results

7 7 7 1 0 0 0 -42 36 0 0 6 6 6 -28
__DATA__
146 : [36 7 7 7 6 6 6 1] [0 0 0 0 0 -28 -42]
74 : [0 7 7 7 6 6 6 1] [36 0 0 0 0 -28 -42]
18 : [-28 7 7 7 6 6 6 1] [36 0 0 0 0 0 -42]
10 : [-42 7 7 7 6 6 6 1] [36 0 0 0 0 0 -28]
[download]

It can be shown that without sorting the data, the following solution is possible:

46 : [7 7 7 1 0 0 0 -42] [36 0 0 6 6 6 -28]
12 : [36 7 7 1 0 0 0 -42] [7 0 0 6 6 6 -28]
2 : [36 0 7 1 0 0 0 -42] [7 7 0 6 6 6 -28]
[download]

This means #1 is also out. Possibly #3 (running it both ways) would produce optimum results but I am not ready to convince myself of it.