divide weights into two groups
Hi, I need to write program which would divite weights into two groups as equal as possible. But I can not think algorithm for this task. Any help?
Find the average of the array and compare the individual values against it. If first is > avg then go here; else go here. This will equate them by weight on each side, but is this what you meant by equal?
Yes, but I think your idea is bad, unless I got it wrong.
For example:
we have weights: 12 13 100 65 14 16 150
avg = 185
So we put in first group till it be < awg?
so group1: 12 13 100 (= 125)
group2: 65 14 16 150 (= 245)
so it is bad :(
It should be:
group1: 100 65 16 (= 181)
group2: 12 13 14 150 (= 189)
For example:
we have weights: 12 13 100 65 14 16 150
avg = 185
So we put in first group till it be < awg?
so group1: 12 13 100 (= 125)
group2: 65 14 16 150 (= 245)
so it is bad :(
It should be:
group1: 100 65 16 (= 181)
group2: 12 13 14 150 (= 189)
Last edited on
I would determine the maximum and decide where it go.
First step: 150 to one side, 100 to another. Next max. is 65 because 100 < 150 it goes to 100 an so on... does it work?
First step: 150 to one side, 100 to another. Next max. is 65 because 100 < 150 it goes to 100 an so on... does it work?
I thought about such idea but it is not good enough:
I sort weights: 150 100 65 16 14 13 12
and put weight to group which is smaller, so we get:
group1: 150 16 13 12 (= 191)
group2: 100 65 14 (= 179)
not good enough :( should be (181 and 189)
I sort weights: 150 100 65 16 14 13 12
and put weight to group which is smaller, so we get:
group1: 150 16 13 12 (= 191)
group2: 100 65 14 (= 179)
not good enough :( should be (181 and 189)
Last edited on
Wow, kind of went out of your way to prove me wrong there didn't ya?
Maikel: It would probably work as long as he doesn't come up with another specific data set designed to find a flaw in your idea, Yeah, I took that personally. You would need a condition in case they became equal. Then another to make sure that if they are equal and the next weight to be added is too large for the remaining weight to balance the two sides out that the function knows what to do.
If you're going through the trouble of nit picking why not be a little more specific in your post?
BTW "not good enough" is better then what you had.
Maikel: It would probably work as long as he doesn't come up with another specific data set designed to find a flaw in your idea, Yeah, I took that personally. You would need a condition in case they became equal. Then another to make sure that if they are equal and the next weight to be added is too large for the remaining weight to balance the two sides out that the function knows what to do.
If you're going through the trouble of nit picking why not be a little more specific in your post?
BTW "not good enough" is better then what you had.
Last edited on
So if I detect equal values I should try to change each element from group1 to groupe2 and leave it if it become more equal then it was? that would work with any weights?
P.S. Sorry, It is not so easy to be very specific when my english is bad...
P.S. Sorry, It is not so easy to be very specific when my english is bad...
Last edited on
To do this as specifically as you want it. You need to know the value of each element already added to each group. You then need to know the differance between the two groups and be aware of the remaining numbers to be added. Being specific in this case is as easy as providing these numbers with your original post. Let me try a few things and get back to you, this is getting to be more interesting then I thought.
I did like maikel said, only added brute force that is trying to change each element from groupe1 with each element in groupe2. It will work with these numbers, but I am not so sure about all posibilities... :(
Last edited on
I assume OP is looking for an algorithm that generates the optimal solution for any arbitrary input without taking an
eternity.
Certainly a starting point is to compute sum the weights and divide by 2 (call this result TW), then find the subset of
elements which sum as close to, without going over, TW. Since this is just another form of the knapsack problem,
it is not N-P complete, so I don't think there is any known algorithm to solve this short of brute force search.
eternity.
Certainly a starting point is to compute sum the weights and divide by 2 (call this result TW), then find the subset of
elements which sum as close to, without going over, TW. Since this is just another form of the knapsack problem,
it is not N-P complete, so I don't think there is any known algorithm to solve this short of brute force search.
Topic archived. No new replies allowed.