J'ai ce problème dans mon manuel: Compte tenu d'un groupe de n articles, chacun avec une valeur distincte V (i), quel est le meilleur moyen de diviser les éléments en 3 groupes afin que le groupe avec la valeur la plus élevée soit minimisé? Donner la valeur de ce plus grand groupe.
Je sais comment faire la variante de pile de ce problème: il faut juste exécuter l'algorithme de sacs à dos à l'envers sur le problème. Cependant, je suis assez perplexe comme comment résoudre ce problème. Quelqu'un pourrait-il me donner des pointeurs?
réponse: à peu près la même chose que le sac à dos 0-1, bien que 2D
3 Réponses :
Problème de devoirs difficile. C'est essentiellement la version d'optimisation du problème de 3 partitions.
http://fr.wikipedia.org/wiki/3-partition_problème < / p>
Il est étroitement lié à l'emballage, la partition et la somme sous-ensemble (et, comme vous l'avez noté, Knapsack). Cependant, il s'agit fortement de NP-complet, ce qui le rend plus difficile que ses cousins. Quoi qu'il en soit, je vous suggère de commencer par regarder des solutions de programmation dynamiques aux problèmes connexes (je commencerais par la partition, mais trouvez une explication non Wikipedia de la solution DP).
mise à jour: je m'excuse. Je vous ai induit en erreur. Le problème à 3 partitions scindre l'entrée en ensembles de 3, pas 3 ensembles. Le reste de ce que j'ai dit s'applique toujours, mais avec le renouvelé espoir que votre variante n'est pas fortement remplie de NP.
@Richieli Question honnête: Combien de détails voulez-vous pour moi de ne pas gâcher le problème? C'est-à-dire la relation de récurrence souhaitée trop (pas que je l'ai, je devrais le faire oublier moi-même)?
Hein, je vais essayer de te faire sortir moi-même. C'est dû dans la soirée, alors je reviendrai à vous si j'ai besoin de plus d'aide.
En fait, j'ai une question: dans le problème de la partition, comment savez-vous quels articles que vous avez déjà utilisés?
Oups. Je viens de re-regarder la définition de 3 partitions. Je vous ai induit en erreur. Toutefois, si vous envisagez de suivre quels numéros sont encore disponibles, vous pouvez utiliser un tableau simple avec 0,1,2,3. Alternativement, utilisez 4 hachons de hashsets pour non attribués, définissez 1, définissez 2 et définissez 3. Gardez également des listes de tri pour chacune des 4 (ou utilisez des structures de données basées sur le tas).
Mise à jour: J'ai une solution de programmation dynamique. Je peux fournir plus de notes si vous en avez besoin. Si vous voulez une énorme indice (spoiler possible), ces notes de cours sur le sous-ensemble Sum vous donnent essentiellement tout ce dont vous avez besoin: sites.cs.queensu.ca/courses/cisc365/record/week06/20111018.h TML
J'ai griffonné un algorithme O (somme ^ 2 * N) sur papier, je vais l'essayer maintenant.
Je me suis rafraîchi périodiquement pour voir si vous avez ajouté une question. Je suppose que votre algorithme a fonctionné. Toutes nos félicitations.
Avez-vous même jumelé un problème de 3 partitions? 3-Partition est la NPC au sens fort, mais cette énoncé de problème est faiblement problématique NPC, signifie qu'il y a un algorithme de temps pseudopoyennomial pour cela.
@Saeedamiri: Pour vous paraphraser, avez-vous même examiné la réponse que vous avez commentée? Non seulement j'ai mis à jour la réponse (30 minutes après avoir posté, 6 mois avant votre commentaire) pour indiquer que c'était non 3 partition, mais j'ai fourni un lien vers une référence qui a des informations sur la manière de résoudre le problème via une programmation dynamique.
@CCOAKLEY, YEP, vous avez corrigé cela, mais éditez votre réponse et supprimez la mauvaise partie. Question similaire posée à nouveau aujourd'hui, et quelqu'un l'a lié à cela, et j'ai lu le premier paragraphe de votre réponse, il n'était en fait pas important pour moi comment le résoudre, il était important de voir une réponse correcte et de près une nouvelle question.
Je ne connais pas "la meilleure" parole mathématiquement parler, mais une approche évidente serait de construire une population de groupes initialement avec un élément de chaque groupe. Ensuite, pour tant que vous avez plus de groupes que le nombre de groupes final souhaité, extrayez les deux groupes avec les valeurs les plus bas et les combiner dans un nouveau groupe que vous ajoutez dans la collection. Ceci est similaire à la construction des arbres de compression de Huffman.
Exemple: P>
1 3 7 9 10 becomes 4(1+3) 7 9 10 becomes 9 10 11(1+3+7)
Nous n'avons pas encore appris cela à ce sujet, alors je ne pense pas tout à fait que je devrais utiliser cela sur ce problème.
Cueillette NIT: L'approche gourmande est optimale dans le boîtier de Huffman (pour un codage variable de longueur d'alphabets fixes). Il effectue raisonnablement une partition uniquement si les chiffres du problème sont distribués bien (où je ne peux pas être plus précis que le mot "bien"). Étant donné que la question a été étiquetée "Programmation dynamique", je suppose que le but de la mission n'était pas d'utiliser une technique gourmande.
Soit f [i] [j] [k] dénote s'il est possible d'avoir donc nous avons et initialement, nous avons pour chaque f [i] [j] [k] [k] = f [i-1] [jv [i]] [k] ou f [i-1] [j] [kv [i] ] .
f [0] [0] [0] = true .
f [i] [j] [k] = true , mettez à jour votre réponse dépend de la manière dont vous définissez
Mais le ith ith pourrait alternativement aller dans le 3ème ensemble, alors je pense que cela devrait être f [i] [j] [k] [k] = f [i-1] [jv [i]] [k] ou f [k] ou f [ I-1] [J] [kv [i]] ou f [i-1] [j] [k] .
En outre, juste pour l'épeler, lorsqu'on considère la solution pour certains I, j, k où f [i] [j] [k] = true, vous calculez le poids du 3ème ensemble en utilisant S [I] - J - k, où s [i] est la somme des poids des premiers items i articles (précomptes en temps linéaire au début).
Comme il est venu et a disparu, voici un exemple d'échec gourmand {100, 51, 49, 40, 30, 20, 10}. La réponse optimale est une fraction parfaite, appliquant de manière gênante l'élément sans signalement le plus grand groupe n'est pas.
J'ai le même manuel. Brian Dean m'a donné à moi;)