Trouver un chemin/des sous-chemins dans un arbre de sorte que la somme des poids soit inférieure à l'entier donné

Question

Étant donné un arbre avec n nœuds (numérotés de 1 à n) et n-1 arêtes. Chaque arête a deux entiers, un poids et un gain, qui lui sont associés. Vous avez également un numéro K. Vous pouvez commencer avec n'importe quel noeud, et vous devez faire des transactions. Dans chaque trade, vous perdez le montant égal au poids du bord et gagnez un profit égal à la valeur de gain du bord. Vous devez maximiser le bénéfice de sorte que le montant total perdu < = K

Voici un lien vers la question d'origine. Le concours correspondant est maintenant terminé.

https://www.hackerrank.com/contests/gs-quantify-2017/challenges/profit-maximization

Ce que je l'ai fait:

J'ai construit une approche récursive en considérant chaque nœud comme nœud à partir du chemin, puis en calculant récursivement le maximum de profit en considérant chacun des noeuds suivants respectueux des lois par le contraintes.

Mais il est évident que cela a une très grande complexité temporelle.

Existe-t-il un moyen plus élégant et plus rapide de le faire?

Answer 1

Voici une suggestion:

1. Choisissez un nœud à proximité du centre du graphique (par exemple en coupant à plusieurs reprises tous les nœuds de feuilles et de choisir le dernier nœud supprimé)
2. déterminer le meilleur profit si la solution utilise ce noeud (pas nécessairement en tant que nœud de départ - il peut juste être au milieu aussi)
3. travail le meilleur profit si la solution utilise chaque sous-arbre à son tour (ie ne pas utiliser le noeud choisi)

Pour calculer le bénéfice d'une solution utilisant un nœud particulier x, vous pouvez utiliser un système de fichiers DFS pour calculer le poids total et le bénéfice pour atteindre chaque nœud.

Ensuite, pour chaque sous-arbre enfant de x:

1. construire une carte triées de poids à profit (ce plan doit être trié en poids croissant)
2. Supprimez toutes les entrées où le profit est inférieur à un précédent le bénéfice (pas de routes maintien des points qui pèsent plus mais donnent moins de profits)

Vous pouvez ensuite fusionner ces sous-arbres pour trouver le maximum de profit de tout itinéraire qui comprend x:

1. Commencez avec la carte Sorted pour enfant 1
2. vers l'avant de itérer sur la carte pour les enfants de 1, et en arrière dans la carte pour les enfants de 2 pour trouver le plus grand profit d'un itinéraire à partir de l'enfant 1 et se terminant par enfant 2.
3. Fusionner les cartes pour enfants 1 et enfant 2, puis répétez l'opération pour enfant 3,4,5 ...

Notez que l'étape 2 et l'étape 3 sont à la fois linéaire du nombre d'entrées en cours de fusion.

S'il y a un facteur de branchement élevé, cette étape de fusion peut devenir trop lente, auquel cas vous pouvez améliorer l'efficacité en fusionnant toujours les deux plus petits sous-arbres au lieu de fusionner dans l'ordre. Une structure de données Heap pourrait être utilisée pour vous dire efficacement quels sont les deux plus petits.

Il se peut qu'il y ait une solution beaucoup plus simple, Hackerrank publie normalement des éditoriaux après un petit moment, donc il vaudrait mieux revérifier votre lien de question dans le futur.