Even and sorted distribution problem

Question

I have a certain number of boxes in a certain order and the number of weights in a certain order. Scales can have different weights (for example, the weight can be 1 kg, another 2 kg, etc.). I want to put the scales in the boxes so that they are evenly distributed as possible weight. I must take the weights in the order in which they are given, and I must fill in the boxes in the order in which they are indicated. That is, if I put the weight in the field n + 1, I can not put the weight in the field n, and I can not put the weight m + 1 in the field until I put the weight m in the field.

I need to find an algorithm that solves this problem for any number of boxes and any set of weights.

A few C # tests with xUnit (Distribute is a method that should solve the problem):

[Fact] public void ReturnsCorrectNumberOfBoxes() { int[] populatedColumns = Distribute(new int[0], 4); Assert.Equal<int>(4, populatedColumns.Length); } [Fact] public void Test1() { int[] weights = new int[] { 1, 1, 1, 1 }; int[] boxes = Distribute(weights, 4); Assert.Equal<int>(weights[0], boxes[0]); Assert.Equal<int>(weights[1], boxes[1]); Assert.Equal<int>(weights[2], boxes[2]); Assert.Equal<int>(weights[3], boxes[3]); } [Fact] public void Test2() { int[] weights = new int[] { 1, 1, 17, 1, 1 }; int[] boxes = Distribute(weights, 4); Assert.Equal<int>(2, boxes[0]); Assert.Equal<int>(17, boxes[1]); Assert.Equal<int>(1, boxes[2]); Assert.Equal<int>(1, boxes[3]); } [Fact] public void Test3() { int[] weights = new int[] { 5, 4, 6, 1, 5 }; int[] boxes = Distribute(weights, 4); Assert.Equal<int>(5, boxes[0]); Assert.Equal<int>(4, boxes[1]); Assert.Equal<int>(6, boxes[2]); Assert.Equal<int>(6, boxes[3]); } 

Any help is much appreciated!

Answer 1

See solution below.

Greetings

Marash

 public static int[] Distribute(int[] weights, int boxesNo) { if (weights.Length == 0) { return new int[boxesNo]; } double average = weights.Average(); int[] distribution = new int[weights.Length]; for (int i = 0; i < distribution.Length; i++) { distribution[i] = 0; } double avDeviation = double.MaxValue; List<int> bestResult = new List<int>(boxesNo); while (true) { List<int> result = new List<int>(boxesNo); for (int i = 0; i < boxesNo; i++) { result.Add(0); } for (int i = 0; i < weights.Length; i++) { result[distribution[i]] += weights[i]; } double tmpAvDeviation = 0; for (int i = 0; i < boxesNo; i++) { tmpAvDeviation += Math.Pow(Math.Abs(average - result[i]), 2); } if (tmpAvDeviation < avDeviation) { bestResult = result; avDeviation = tmpAvDeviation; } if (distribution[weights.Length - 1] < boxesNo - 1) { distribution[weights.Length - 1]++; } else { int index = weights.Length - 1; while (distribution[index] == boxesNo - 1) { index--; if (index == -1) { return bestResult.ToArray(); } } distribution[index]++; for (int i = index; i < weights.Length; i++) { distribution[i] = distribution[index]; } } } } 

Answer 2

Second attempt: I think that the A * algorithm (pronounced "star") will work well here, even if it consumes a lot of memory. you warrant an optimal response, if one exists.

Each “node” you are looking for is a possible combination of box scales. The first node should be any weight that you choose at random, put in a box. I would recommend collecting new scales at random.

Unfortunately, A * is quite complicated, and I don't have time to explain it here. It is easy enough to understand it by reading it yourself, but to compare it with this problem, as I described above, will be more difficult. Please answer the questions if you choose this route.