Problème de distribution uniforme et trié

Question

J'ai un nombre donné de boîtes dans un ordre spécifique et un nombre de poids dans un ordre spécifique. Les poids peuvent avoir des poids différents (par exemple, un poids peut peser 1 kg, un autre 2 kg, etc.). Je veux mettre les poids dans les boîtes de manière à ce qu'ils soient aussi répartis que possible en poids. Je dois prendre les poids dans l'ordre où ils sont donnés et je dois remplir les cases dans l'ordre qui leur est donné. C'est à dire si je mets un poids dans la case n + 1 je ne peux pas mettre un poids dans la case n, et je ne peux pas mettre le poids m + 1 dans une case avant d'avoir mis le poids dans une case.

J'ai besoin de trouver un algorithme qui résout ce problème pour n'importe quel nombre de boîtes et n'importe quel ensemble de poids.

Quelques essais en C# avec xUnit (Distribuez est la méthode qui devrait résoudre le problème):

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

Toute aide est grandement appréciée!

Answer 1

Deuxième tentative: je pense que l'algorithme A * (prononcé "une étoile") fonctionnerait bien ici, même s'il consommerait beaucoup de mémoire. vous êtes assuré d'obtenir une réponse optimale, s'il en existe une.

Chaque "noeud" que vous recherchez est une combinaison possible de poids dans des boîtes. Le premier nœud devrait être n'importe quel poids que vous choisissez au hasard, mis dans une boîte. Je recommanderais de choisir de nouveaux poids de façon aléatoire. Malheureusement, A * est assez complexe pour que je n'aie pas le temps de l'expliquer ici. Il est assez facile à comprendre en lisant par vous-même, mais le mapper à ce problème comme je l'ai décrit ci-dessus sera plus difficile. S'il vous plaît poster des questions à ce sujet si vous choisissez cette route.

Answer 2

Voir la solution ci-dessous.

Cheers,

Maras

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