一個均勻的和有序的分佈問題

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