Algorithm: Two Piles

+determining efficiency.

Page 1 of 1

3 Replies - 4124 Views - Last Post: 31 March 2007 - 09:34 AM

#1 qdoom  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 82
  • Joined: 31-August 06

Algorithm: Two Piles

Posted 09 February 2007 - 08:19 AM

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.

Is This A Good Question/Topic? 0
  • +

Replies To: Algorithm: Two Piles

#2 spullen  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 10
  • View blog
  • Posts: 356
  • Joined: 22-March 07

Re: Algorithm: Two Piles

Posted 22 March 2007 - 09:04 PM

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)?
Was This Post Helpful? 0
  • +
  • -

#3 alpha02  Icon User is offline

  • Sexy DIC God
  • member icon

Reputation: 47
  • View blog
  • Posts: 803
  • Joined: 20-May 06

Re: Algorithm: Two Piles

Posted 23 March 2007 - 07:23 AM

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 March 2007 - 07:23 AM

Was This Post Helpful? 0
  • +
  • -

#4 qdoom  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 82
  • Joined: 31-August 06

Re: Algorithm: Two Piles

Posted 31 March 2007 - 09:34 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1