différence minimale entre la somme de deux sous-ensembles
Gens,
tombé sur un problème... trouvé cela interessant... suis en le modifiant un peu juste tu pep.
Étant donné un ensemble d'entiers (gamme 0-500), trouver le minimum de différence entre la somme de deux sous-ensembles qui peuvent être formées par le partage à peu près également. (dire le comte d'entiers n, si n est pair, chaque jeu doit avoir n/2 éléments, et si n est impair, on a (n-1)/2 éléments et d'autres a (n+1)/2 éléments)
échantillon imput : 1 2 3 4 5 6
différence minimale = 1 (sous-ensembles étant de 1 4 6 2 3 5 )
d'entrée d'échantillon 2 : [ 1 1 1 1 2 2 2 2 ]
différence minimale = 0 (sous-ensembles 1 1 2 2 et 1 1 2 2 )
est là DP approche pour résoudre ce problème.
Merci les gars...
raj...
source d'informationauteur Rajan
Vous devez vous connecter pour publier un commentaire.
Ce problème ressemble presque à de la "partition équilibrée".
Vous pouvez utiliser une approche DP pour construire une pseudo-polynomial en temps de l'algorithme qui permet de résoudre l'équilibre de la partition. Voir le problème 7 à http://people.csail.mit.edu/bdean/6.046/dp/
Il semble que vous pourriez avoir une approche similaire.
J'ai résolu ce problème récemment, à l'aide de la Programmation Dynamique en c++. Je n'ai pas modifié le code pour répondre à votre question. Mais la modification de certaines constantes et peu de code devrait le faire.
Le code ci-dessous se lit et se résout N problèmes.Chaque problème a certaines personnes (dans votre cas nombre d'entiers) et leur poids (valeurs entières). Ce code tente de diviser l'ensemble en 2 groupes avec une différence minimum.
Une bonne façon de penser à propos de ce serait, si vous avez eu une DP solution à ce problème, pourriez-vous l'utiliser pour répondre somme de sous-ensemble dans un P laps de temps? Si oui, alors votre DP solution n'est probablement pas correcte.
Ce qui semble être une instance de la Partition problèmequi est NP-Complet.
Selon l'article de Wikipedia, il y a une pseudo-polynomial en temps de programmation dynamique de la solution.
J'ai écrit ce programme en C++ en supposant que max somme pourrait être 10000.
Prochaine étape, je voudrais essayer de trouver une paire de nombres opposés de listes avec la différence, la moitié des sommes " la différence (ou proche) et le swap.