I think what you have is a "multiple" knapsacks problem. (Find a link that works for you if not this one).

Solving a Multiple Knapsacks Problem | OR-Tools | Google for Developers[^]

15,998,126 members

Hi,

This is difficult one to explain but here goes. I have a list of numbers which are to be set over a set number of column (Pre-determined by another calulation). The task it to move the number around till the shortest column height (Numbers are additionalised in each column to give height).

I told you it was not going to be easy to explain.

What is the best way to process this to get the column lists?

Ex:- Numbers (232,277,432,200,200,220,500,490,286,478) & Column Count is 4 (Note:- Not always are they evenly balanced by quantity).

Think of it as you can move the numbers from column to column but the aim to to get the lowest average of the sum of the column across all columns.

Ideal would (Not as per example):- Col=200,300,300 Col2=200, 400, 100, 50 Col3= 200, 300, 200 Col4=300, 200, 50, 200

Column sum

Col1=800

Col2=750

Col3=700

Col4= 750

i.e. move the lengths around to make the shortest column.

Thanks in advance.

OK, Realtime numbers

432

432

432

305

205

205

205

205

205

205

150

150

150

4 columns/pots (making an target 820 per each pot)

I hope this helps

**What I have tried:**

Sorry I have no trys to show as I must confess I don't realy know where to start (Any pointer are welcome).

New Try,

1) Order list to larger -> Smaller

2) Workout the Best average.

3) Add to each column (In order) largest

4) when all have first run add smallest to largest but not if largest is greater or equal to Best average.

I'm unsure if this is the best approach but it is best way I can visualise the process. Turning it into code is another issue.

Hi, Sorry for the delay in writting this up.

I have worked out a solution from the input here & thought it good to pass it on where I got to (If someone has a simular issue it may come in handy)

Steps:-

1) Sort coins with larger first.

2) Add one coin to each pot (From larger to Smaller) i.e. only one coin per pot at this stage.

3) Put the largest coin in the smallest pot till all coins have gone.

This worked for me & I hope it works for others.

This is difficult one to explain but here goes. I have a list of numbers which are to be set over a set number of column (Pre-determined by another calulation). The task it to move the number around till the shortest column height (Numbers are additionalised in each column to give height).

I told you it was not going to be easy to explain.

What is the best way to process this to get the column lists?

Ex:- Numbers (232,277,432,200,200,220,500,490,286,478) & Column Count is 4 (Note:- Not always are they evenly balanced by quantity).

Think of it as you can move the numbers from column to column but the aim to to get the lowest average of the sum of the column across all columns.

Ideal would (Not as per example):- Col=200,300,300 Col2=200, 400, 100, 50 Col3= 200, 300, 200 Col4=300, 200, 50, 200

Column sum

Col1=800

Col2=750

Col3=700

Col4= 750

i.e. move the lengths around to make the shortest column.

Thanks in advance.

OK, Realtime numbers

432

432

432

305

205

205

205

205

205

205

150

150

150

4 columns/pots (making an target 820 per each pot)

I hope this helps

Sorry I have no trys to show as I must confess I don't realy know where to start (Any pointer are welcome).

New Try,

1) Order list to larger -> Smaller

2) Workout the Best average.

3) Add to each column (In order) largest

4) when all have first run add smallest to largest but not if largest is greater or equal to Best average.

I'm unsure if this is the best approach but it is best way I can visualise the process. Turning it into code is another issue.

Hi, Sorry for the delay in writting this up.

I have worked out a solution from the input here & thought it good to pass it on where I got to (If someone has a simular issue it may come in handy)

Steps:-

1) Sort coins with larger first.

2) Add one coin to each pot (From larger to Smaller) i.e. only one coin per pot at this stage.

3) Put the largest coin in the smallest pot till all coins have gone.

This worked for me & I hope it works for others.

Comments

I think what you have is a "multiple" knapsacks problem. (Find a link that works for you if not this one).

Solving a Multiple Knapsacks Problem | OR-Tools | Google for Developers[^]

Solving a Multiple Knapsacks Problem | OR-Tools | Google for Developers[^]

Permalink

Share this answer

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900

Thanks for the reply, As I said it is difficult to explain. I Have updated the question. Hopefully helps

Also please explain among other why Col2 results in 700 (and not what I would assume in 750)

I will look at the examples but I'm unsure of the output as it is optermisation (Not realy something I can workout). Thanks again.

Another way to look at this is you have a bag of coins (differant values) & 4 pots. The output result is to fill in the pots with an ammount of coins (coins can only go in one pot & can't be copied) so that the total coin value in each pot in the lowest value accross the pots. There will in most cases be a variation between pot totals but if this kept to a miniumum.(i.e. on ex.2 varition of 100). If seen on a bar graph the bars should be the lowest average height. Does this help?

Distribute the M coins with individual values into N (e.g. here N = 4) pots in a way that every of the N pots contain nearly the same quantity.

In other words:

a.) We have M coins with individual values. Let us call the sum of them is SM.

b.) We have N pots

c.) The optimal distribution of the M coins into the N pots is when every pot holds SM/N 'coin values'

Correct?

[Edit]

It makes it easier, if you click to 'Reply' on a post, other than to use 'Have a Question or Comment'.

My thoughts are now looking at targeting the optimal (SM/N) by largest to smallest. I'm still in the dark.

It looks pretty like a optimization request. The brute force solution will be to solve it with a downhill algorithm. But I think it is overkill. As I mentioned I need some time.

And you are very welcome with a question that challenges the brain ;)

You calculate every possible distribution of the M coins into the N bags.

The combination for which Delta= Sqrt(Sum((Bag_i - SM/N)^2)) is minimal wins.

Not nice, but maybe a solution.