Comment diviser une liste d'éléments en partitions égales en fonction du poids de l'objet?

Question

J'ai une liste d'éléments qui est un peu comme ceci:

[ 
    ["orange", 9], 
    ["watermelon", 3], 
    ["grapefruit", 6], 
    ["peach", 8], 
    ["durian", 2], 
    ["apricot", 6] 
] 

Je voudrais partager cette liste en ... dire deux groupes pour que la somme des poids des éléments de chaque groupe sont les égale que possible, à savoir:

List 1: 
    orange: 9 
    durian: 2 
    apricot: 6 
    TOTAL: 17 

List 2: 
    watermelon: 3 
    grapefruit: 6 
    peach: 8 
    TOTAL: 17 

Actuellement, je suis résoudre ce en parcourant la liste ordonnée de manière zigzag'esque. Affectation des objets avec plus de poids dans la première passe à chaque groupe, en affectant les objets avec moins de poids sur la deuxième passe, et ainsi de suite.

Cela fonctionne bien, mais il a des défauts. Je pense qu'un second passage sur les groupes dans lesquels j'échangerais des objets se traduirait par des groupes plus équitablement répartis, mais le code impliqué pourrait devenir trop compliqué. Est-ce que quelqu'un sait d'une manière plus efficace ou intelligente de faire ceci?

Merci!

Answer 1

Ceci est la version d'optimisation du partition problem, qui est NP-complet, bien que, selon cet article, "il existe des heuristiques qui résolvent le problème dans de nombreux cas, de manière optimale ou approximative".

La section methods de cet article contient un certain nombre de façons de faire des solutions approximatives ou pseudo-polynomiales. Plus précisément, si vous pouvez vivre avec une réponse approximative, vous pouvez essayer l'approche gourmande:

Une approche du problème, imitant la façon dont les enfants choisissent des équipes pour un jeu, est l'algorithme glouton, qui passe par les chiffres dans l'ordre décroissant, assignant chacun d'entre eux à quel sous-ensemble a la plus petite somme.

Le temps d'exécution de cette approche est de O(n^2) et garantit que vous atteindrez un facteur de 4/3 de la solution exacte.

Si vous devez avoir une solution exacte et que votre jeu de données est suffisamment petit, vous pouvez toujours utiliser une approche de force brute pour générer toutes les possibilités (c'est exponentiel, O(2^n)). En fonction de vos besoins de performance, cela peut suffire.

Answer 2

Vous pouvez totaliser tous les poids, diviser par le nombre de groupes, atteindre un poids cible, puis parcourir les articles par ordre décroissant de poids en les jetant dans le même groupe s'ils correspondent au poids cible et dans l'autre groupe s'ils ne le font pas.

Il y a probablement quelques maths là-bas qui peuvent trouver une preuve formelle de la meilleure façon de le faire, mais c'était ma pensée au sommet de ma tête.

Answer 3

Cela ne fonctionnera pas. Par exemple, S = {5, 5, 4, 3, 3}.