Today, I received my first task in "Algorithms and data structures". It's the first one, so it's quite an easy one (and we didn't even have our first real theoretical lecture on this topic (next week)). I need to write a program: N items. The program needs to divide them as equally (weight) as possible in to two piles.

On the way home from university, I came up with a couple of ways to do it. Backtracking seems to be the obvious solution. Another thing, that I came up with:
Sort the items (heaviest -> lightest). Take the heaviest, put it in the first pile. Take the 2nd heaviest, put it in the second pile. Take the 3rd heaviest, put it in the pile, that currently is lighter etc. This doesn't always solve it correctly, but it's always at least very close. For example:
We have items, that weight: 15 7 9 6 19 3 5
Sortet: 19 15 9 7 6 4 3
1st pile: 19(1) 7(4) 4(6) 3(7)
2nd pile: 15(2) 9(3) 6(5)
The best piles would be: 1st pile: 19 9 4. 2nd pile: 15 7 6 3
Maybe there is a way to use this algorithm as some kind of early-solver+limiter-to-make-further-solving-quicker. I'm not sure yet.

So here's my first question: should I just use backtracking or is there a better way to do this task?

My second question: what's the best way to check the efficiency of algorithms/programs? For example, in this situation, should I just create a file with a lot of weights (the weights are read from the file) and measure the time? And what's the best way to check the memory usage? Maybe there's some kind of program, that measures these things?

Thanks.

Are you trying to sort them, or are you trying to just divide the list of items into 2 at some location in the list that will be close in weight to each other (meaning the two sets are almost equal)?

First of all, get the sum of all items and divide it by 2 to find out how much we need in each pile. Example:

1, 4, 8, 2, 6, 8, 9

Total: 38
In each pile: 38/2 = 19

Now find some items that give 19 as a total.
I thought about:
2, 8, 9
1, 4, 6, 8

This should lead you on the right path, ask me if you need more explanations. Hope this helps.

This post has been edited by alpha02: 23 Mar, 2007 - 06:23 AM

Thanks for the answers. Sadly, they came more than month after I finished the task and got the grade. (20+3/20 = max)
I appreciate your desire to help.