algorithme pour trier des nombres en ensembles qui ont une somme spécifique

Question

J'ai 27 bandes de plancher de bois dur de différentes longueurs de 18 à 48 pouces. Je veux faire 3 planches composées chacune de 3 rangées de planchers. Deux planches doivent mesurer 60 "de long et une autre planche 72". La longueur totale de toutes les bandes est suffisante pour construire ces planches. Évidemment, je pouvais sélectionner les bandes au hasard, les coller et les couper à la taille. Cependant, je voudrais minimiser la quantité de déchets coupés.

Le problème peut être reformulé plus simplement: J'ai 27 entiers et j'aimerais les trier en 9 ensembles. Chacun des 6 ensembles ajoute jusqu'à 60 et chacun des trois ensembles restants s'ajoutent à 72. Ce problème est une variation du problème de la somme des sous-ensembles.

J'ai trouvé quelques articles traitant de 'dynamic programming' mais je ne connais rien à cette approche et encore moins à la façon de la coder.

Un problème de similar a été posé il y a quelque temps mais la discussion manque.

Mon approche est la «méthode google». Force brute. Calculez tout. trier plus tard. Donc,

groupe les nombres entiers dans 9 tableaux de 3 nombres. Notez qu'il y a 9!/3! = 60480 groupements.

pour chaque groupe calculer la somme de chaque tableau, appelez cela le ArraySum. Il y en a 9.

(A,B,C,D,E,F,G,H,I) 

calculer la différence des sommes cibles (72,60,60)

A-72,B-72,C-72, D-60, E-60,... 

Additionnez toutes les différences pour ce groupe et de stocker ce numéro (appeler GroupSum). C'est le nombre que je veux minimiser.

Permute les Différences entre les paires ArraySums et Target donne Sums (9!/3! = 60480)

maintenant revenir en arrière, changer le regroupement et la répétition. Je reçois 60480 x 60480 GroupSums = 3657830400

Triez les groupes, trouvez le groupe le plus bas, choisissez ce groupe.

Existe-t-il un meilleur moyen que le précalcul et le tri?

Answer 1

À moins que je l'ai mal compris quelque chose, il semble hors de propos que vous les regrouper aussi longtemps que vous pouvez trouver un groupe qui fonctionne tout (là où tous les groupes sont au moins la longueur requise)

La logique étant que vous commencez avec exactement la quantité requise de bandes, ce qui signifie que vous aurez besoin de tous les utiliser, peu importe quoi. La longueur totale de la bande dont vous avez besoin est constante (60 * 6 + 72 * 3) et donc la longueur totale que vous utiliserez (quelle que soit la somme de vos 27), donc le gaspillage est une constante - quelle que soit la différence est. Si je comprends bien, un algorithme glouton devrait faire l'affaire - il suffit d'utiliser la combinaison qui vous donne le résultat minimum pour chaque planche donnée, de résoudre arbitrairement les liens et de passer à la suivante. A moins que vous ne souhaitiez minimiser la quantité de bandes à découper, c'est-à-dire répartir tous les "déchets" en autant de bandes que possible. Dans ce cas, vous devez utiliser une fonction de perte L0, pas L1 comme vous le proposez (c'est-à-dire que vous voulez minimiser le nombre de sommes! = 0, plutôt que la valeur de la somme elle-même)