PHP Calculer les tableaux équilibrés

Question

Ok, je ne suis pas sûr que le titre soit aussi efficace, mais c'est le meilleur que je puisse trouver.

Fondamentalement, voici le scénario.

J'ai 11 catégories. Dans chaque catégorie, j'ai des articles, mais une catégorie pourrait avoir 1 article, 1 pourrait en avoir 20.

Maintenant, je veux séparer les 11 catégories en 5 piles ou colonnes. Je souhaite que chacune des piles contienne une quantité égale ou presque égale d'articles et qu'aucun article de catégories ne puisse déborder d'une pile.

Donc, étant donné les données suivantes:

Category | Items 
------------------------- 
Cat 1 | 10 
Cat 2 | 3 
Cat 3 | 7 
Cat 4 | 11 
Cat 5 | 5 
Cat 6 | 13 
Cat 7 | 19 
Cat 8 | 5 
Cat 9 | 3 
Cat 10 | 9 
Cat 10 | 15 

Total = 100 Items 

donc je veux les éléments à répartir équitablement entre les piles.

Il y a 5 piles pour être égales, il devrait y avoir 20 articles par pile. Mais il y a le problème, les objets de 1 pile ne peuvent pas déborder. Alors, comment puis-je calculer les données à quelque chose comme de sortie ceci:

Stack 1|Stack 2|Stack 3|Stack 4|Stack 5 
-------|-------|-------|-------|------- 
Cat 10 |Cat 1 |Cat 11 |Cat 6 |Cat 7 
Cat 4 |Cat 3 |Cat 8 |Cat 9 | 
     |Cat 2 |  |Cat 5 | 

20  20  20  21  19 

Il n'a pas d'importance quelle catégorie est où la pile tant que les articles sont répartis le plus équitablement entre les piles.

Maintenant, les résultats de ce calcul de pile seront mis en cache car je n'aurai pas besoin de calculer très souvent, donc si la solution est très lourde en CPU, postez-la toujours.

Merci :)

Answer 1

Ce problème havresac. http://en.wikipedia.org/wiki/Knapsack_problem Il existe de nombreuses ressources problème de google knapsack

Un moyen simple est d'essayer toutes les combinaisons possibles. Chaque combinaison que vous calculez calcule également l'écart-type. Utilisez l'écart-type pour enregistrer la meilleure combinaison.