9
votes

Fractionnement des valeurs dans des groupes uniformément

Permettez-moi d'essayer d'expliquer la situation du mieux que je peux.

permet de dire que j'ai 3 valeurs xxx

je dis un algorithme de diviser ces valeurs en x colonnes x . Disons X = 2 pour clarification.

L'algorithme détermine que le groupe de valeurs est mieux placé dans deux colonnes de la manière suivante. xxx p> Chaque colonne a une valeur de nombres paires (totaux, non littéraux).

permet maintenant de dire que j'ai les valeurs suivantes xxx

Je dis à l'algorithme que je veux Valeurs divisées en 3 colonnes. L'algorithme me dit maintenant que ce qui suit est le meilleur ajustement. xxx

remarque comment les colonnes ne sont pas silencieuses, mais c'est aussi proche que possible. Un peu plus et un peu sous est considéré comme ok, tant que la liste est aussi proche de même que possible.

Quelqu'un a eu des suggestions? Connaître de bonnes méthodes de faire cela?

algorithm sorting

0 commentaires

3 Réponses :

3
votes

Si vous voulez exactement les mêmes valeurs, alors pour le nombre de colonnes x = 2, c'est le classique Problème qui est NP-complet, mais a des solutions pseudo-polynomiales.

Plus de colonnes (c'est-à-dire x> 2), et cela devient fortement complet NP. Problème de 3 partitions .

pour x> 3, je soupçonne que ce sera toujours fortement np-complet.

Étant donné que le problème de la partition X peut être réduit à votre problème, cela sera aussi difficile que les problèmes ci-dessus.

Vous auriez probablement besoin de méthodes heuristiques pour vous aider.

0 commentaires

4
votes

Je le ferais comme ceci:

Ajoutez toutes les valeurs, appelons ceci s
Divisez S par le nombre de colonnes, appelons ceci m.
Recherchez un ensemble de valeurs dont la somme est m ou aussi près que possible de M, à l'aide d'un algorithme de sacs à dos (par exemple, http://search.cpan.org/~andale/algorithm-knapsack-0.02/napsack.pm (juste un Google rapide sur Knapsack))
Prenez la somme de l'ensemble des valeurs et soustrayez-la de S, appelons-le t.
Divisez T par le nombre de colonnes moins 1
et répétez l'algorithme

0 commentaires

2
votes

J'ai répondu à une question similaire au dos.

Je peux penser à une solution sous-optimale gourmande.

Trier les chiffres Diminution de la commande de commande. (Les plus petits numéros surprennent moins tellement les traiter plus tard)
Décidez du nombre d'ensembles que vous allez avoir. pas trop sûr de cette
passe par les éléments définis un par un et mettez-les dans le sous-ensemble qui a la somme la plus basse (rond robin en cas d'égalité des sommes)
Cela ne va jamais vous donner la solution optimale.
Pour votre cas, 8 7 4 3 1 serait la commande. Et vous auriez (heureusement) obtenez les mêmes résultats que vous avez mentionné.
8 = 8
7 1 = 8
4 3 = 7
Cela ne vous donnera pas toujours la solution optimale

1 commentaires

C'est une excellente solution heuristique qui évite l'utilisation de n'importe quel paramètre de réglage et est très facile à programmer. En utilisant un knapacacier sur un sous-ensemble itératif des éléments de risque que nous quitterons de nombreux éléments jusqu'à la fin et semble être une douleur à mettre en œuvre. Cela semble beaucoup plus robuste.