Après quelques nuits bien remplies, ma tête ne fonctionne pas si bien, mais cela doit être corrigé hier, alors je demande à la communauté la plus rafraîchie.
J'ai une série de chiffres. Par exemple:
1, 5, 7, 13, 3, 3, 4, 1, 8, 6, 6, 6
J'ai besoin de diviser cette série en trois parties afin que la somme des chiffres dans toutes les parties soit aussi proche que possible. L'ordre des chiffres doit être maintenu, de sorte que la première partie doit être composée des premiers chiffres X, le deuxième - des chiffres suivants et la troisième de tout ce qui reste.
Quel serait l'algorithme de faire cela?
(Remarque: le problème réel consiste à organiser des paragraphes de texte de hauteurs différentes en trois colonnes. Les paragraphes doivent maintenir l'ordre (bien sûr) et ils ne peuvent pas être divisés en deux. Les colonnes doivent être aussi égales de hauteur que possible.)
5 Réponses :
Je crois que cela peut être résolu avec Un algorithme de programmation dynamique pour la rupture de ligne inventée Par Donald Knuth pour une utilisation dans Tex.
Intéressant, mais cet algorithme s'appuie sur une taille de ligne maximale connue. Mes colonnes n'ont pas de limite - elles doivent simplement être aussi proches les unes des autres que possible, pour donner un résultat esthétiquement agréable.
Je pense que cet algorithme est de briser une séquence de nombres dans n'importe quel nombre de segments, chacune de laquelle la somme est à la plupart des k et de taille similaire les unes des autres que possible. Ce que nous voulons ici, il est de casser la séquence dans un nombre fixe de segments (3) qui sont aussi semblables que possible les uns les autres que possible, ce qui est légèrement différent. Mais il pourrait toujours être utile d'essayer de définir K = somme / 3 ou à peu près.
Trouver Somme et Obtenez A = Somme / 3
puis localisez le plus proche A, 2 * A dans la somme cumulative qui divise votre liste en trois parties égales.
Après AMDHUSET Réponse, j'ai précédemment répondu à cette question sur SO.
Word Wrap to X lignes au lieu de la largeur maximale (moindre déchirure) p>
Cet algo ne s'appuie pas sur la taille de la ligne max mais donne une coupe optimale. P>
Je l'ai modifié pour travailler avec votre problème: p> Le résultat que j'ai obtenu est: p> [1, 5, 7, 13] 26
[3, 3, 4, 1, 8] 19
[6, 6, 6] 18
[[1, 5, 7, 13], [3, 3, 4, 1, 8], [6, 6, 6]]
Uff, python. Pas l'une des langues que je connaisse très bien. Prendra un certain temps pour ronger. Je suis tenté de commencer par la solution de Lior Kogan, de lancer une fonction de coût différente et de quelques optimisations pour réduire le nombre de boucles. Étant donné que ma série sera généralement courte (20 articles en sont un grand), un algorithme quadratique n'est pas tout ce mal même. Mais dans la moyenne - avoir un uppote! :)
@ Vilx- J'ai essayé d'écrire un algo qui suit étape par étape le programme dynamique du moindre déchiqueté, de sorte qu'il ne devrait donc pas être très difficile à comprendre. Mais vous pouvez trouver beaucoup de versions (surtout en C #) de ce code dans le lien que j'ai publié sur le dessus de ma réponse.
Merci. C # est ma chose en effet. :)
Il h. Délicieux. Comme j'écris ma propre solution basée sur Lior Kogan, mais avec quelques optimisations, j'arrive lentement et la compréhension de la solution proposée par vous. :)
permet de dire que p est votre matrice de hauteurs de paragraphe; Vous obtiendrez l'index de démarrage de la 2e et 3ème séquence. Notez son type de pseudo code :)
Premièrement, nous devrons définir le but mieux:
Supposons que les sommes partielles sont A1, A2, A3, nous essayons de minimiser | A-A1 | + | A-A2 | + | A-A3 | + | A-A3 | + | A-A3 | + | A-A3 | + | A-A3 |. A est la moyenne: A = (A1 + A2 + A3) / 3.
Par conséquent, nous essayons de minimiser | A2 + A3-2A1 | + | A1 + A3-2A2 | + | A1 + A2-2a3 |.
Sonsons la somme (qui est constante): S = A1 + A2 + A3, donc A3 = S-A1-A2.
Nous sommes en essayant de minimiser:
| A2 + S-A1-A2-2A1 | + | A1 + S-A1-A2-2A2 | + | A1 + A2-2S + 2A1 + 2A2 | = | S- 3A1 | + | S-3A2 | + | 3A1 + SA2-2S |
désignant cette fonction comme f, nous pouvons faire deux boucles O (n ^ 2) et garder une trace du minimum:
quelque chose comme:
Eh bien, c'est simple. Et je vois comment cela pourrait être adapté à une autre "fonction de coût", semblable à l'algorithme de Knuth. Non efficace, mais des améliorations peuvent être apportées. D'autre part - je vais rarement (si jamais) obtenez plus de 20 groupes de toute façon, alors peut-être que cela est même le meilleur en termes de maintenabilité.
au-dessus de l'algo est en réalité [BRUTE FORCE ALGO] O (N ^ 3), N ^ 2 pour deux boucles et n pour la somme dans la boucle interne.
@ vikas368: En réalité non. Vous devez juste ajouter un seul élément dans chaque itération. Je l'ai écrit de cette façon que pour la clarté.
d'accord. Si vous faites la somme itérative, son O (n ^ 2), convenu. Merci de clarifier
Dupliquer la question? Stackoverflow.com/questions/3009146/...
Fermer, mais celui-ci permet une réaménagement des valeurs. Je pense que mon cas devrait être plus simple, mais l'algorithme mentionné il n'y a pas d'utile ici.
Trois parties - Est-ce l'exigence, ou seulement un exemple?
Exigence. Mais je pense qu'un algorithme approprié devrait pouvoir gérer un nombre arbitraire de colonnes. Néanmoins, si vous devez prendre 3 comme une valeur spéciale pour le faire faire - par tous les moyens, faites-le.