Четкая и отсортированная проблема распространения

Question

У меня есть определенное количество ящиков в определенном порядке и несколько весов в определенном порядке. Весы могут иметь разные веса (например, вес может составлять 1 кг, еще 2 кг и т. Д.). Я хочу поместить весы в ящики таким образом, чтобы они были равномерно распределены как возможный вес. Я должен брать веса в том порядке, в котором они даны, и я должен заполнить коробки в том порядке, в котором они указаны. То есть, если я поместил вес в поле n + 1, я не могу поместить вес в поле n, и я не могу поместить вес m + 1 в коробку, пока я не поместил вес m в коробку.

Мне нужно найти алгоритм, который решает эту проблему для любого количества ящиков и любого набора весов.

Несколько тестов в C# с XUnit (Распределить это метод, который должен решить проблему):

[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]); 
    } 

Любая помощь очень ценится!

Answer 1

Вторая попытка: я думаю, что алгоритм A * (произносится как «звезда») будет хорошо работать здесь, даже если он будет потреблять много памяти. вам гарантированно получить оптимальный ответ, если он существует.

Каждый «узел», который вы ищете, представляет собой возможную комбинацию весов в коробках. Первым узлом должен быть любой вес, который вы выбираете наугад, помещаете в коробку. Я бы рекомендовал собирать новые весы в случайном порядке.

К сожалению, A * достаточно сложна, чтобы у меня не было времени объяснить это здесь. Его достаточно легко понять, прочитав самостоятельно, но сопоставление его с этой проблемой, как я описал выше, будет более сложным. Пожалуйста, ответьте на вопросы, если вы выберете этот маршрут.

Answer 2

См. Решение ниже.

Приветствия,

Мараш

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]; 
      } 
     } 
    } 
}