Comment implémenter un tel algorithme?

Question

Dites qu'il y a x nombre de boîtes, chaque boîte contient un "inventaire" des lettres A-Z, chaque inventaire de lettres étant 1 ou plus.

Maintenant, dis-je besoin:

• 6 Comme
• 2 hôtes
• 1 C

Comment puis-je obtenir une liste de toutes les combinaisons possibles/permutation des boîtes cela peut me fournir les lettres dont j'ai besoin?

L'algorithme doit également produire une combinaison de boîtes pour répondre à mes besoins. Par exemple: disons que Box-1 n'a que 4 As et que Box-2 a 1 A et que Box-3 a 1 A, j'ai besoin du résultat de l'algorithme pour spécifier que le 6 As peut être rempli sur les 3 cases.

Quelle est la logique de base à la solution d'un tel problème. Y a-t-il des algorithmes particuliers que je dois examiner pour cela?

EDIT 1:

par la suggestion de dcp, voici ma tentative que la mise en œuvre de PHP:

$boxes = array(
    // box 1 
    array(
     'A' => 6, 
     'B' => 4, 
     'C' => 10 
    ), 
    // box 2 
    array(
     'A' => 8, 
     'B' => 4, 
     'C' => 2 
    ), 
    // box 3 
    array(
     'A' => 1, 
     'B' => 1, 
     'C' => 0 
    ) 
); 

$n = count($boxes); 

for ($mask = 0; $mask <= (1 << $n) - 1; $mask++) 
{ 
    $tots = array(); 
    for ($i = 0; $i < $n; $i++) 
    { 
     if (((1 << $i) & $mask) != 0) 
     { 
      // this is a selected box for this mask, add the A's, B's etc. for this box to the total 
      $tots[0] += $boxes[$i]['A']; 
      $tots[1] += $boxes[$i]['B']; 
      $tots[2] += $boxes[$i]['C']; 
     } 
     // check the tots array to see if it meets the letter requirements. If it does, 
     // then this is a valid combination of boxes. 
    } 
} 

Answer 1

Si le nombre de boîtes est assez petite, disons 25 ou moins, vous pourriez utiliser un masque de bits pour la force brute sur toutes les combinaisons de boîtes possibles:

// assume n is number of boxes, and boxes is the array of boxes 
for(int mask = 0; mask <= (1<<n)-1; ++mask) { 
    int tots[26]; 
    for(int i = 0; i < n; ++i) { 
    if (((1<<i)&mask) != 0) { 
     // this is a selected box for this mask, add the A's, B's etc. for this box to the total 
     tots[0] += number of A's in box i 
     tots[1] += number of B's in box i 
     . 
     . 
    } 
    // check the tots array to see if it meets the letter requirements. If it does, 
    // then this is a valid combination of boxes. 
    } 
}