Maximale Teilbaumsumme im Baum mit begrenzter Länge

Question

Ich habe eine Baumstruktur. Die Aufgabe ist es, die größte Summe/Gewicht von Pfad Knoten zu finden, aber ich kann nur n mal verschieben. Das ist ok, aber "nach oben"/"zurück" kostet nichts. Wie kann ich das erreichen?

Unten ist mein Code, aber das Problem ist, dass auf jeden Knoten nur einmal zugegriffen werden kann, so dass es nicht funktioniert.

int mSum(Node* node, int mvLeft) { 
    if (node == nullptr) { return 0; } 
    if (mvLeft == 0) { return node->value; } 
    mvLeft--; 
    int sum = max(mSum(node->left, mvLeft), mSum(node->right, mvLeft)); 
    return node->value + max(sum, mSum(node->parent, mvLeft + 1)); 
} 

Hier ist das Beispieldiagramm. Die Zahlen auf den Knoten stellen die Kosten dar, um dorthin zu gelangen. Jeder Knoten kann nur einmal besucht werden, außer "zurück" gehen.
Die n Schritt Grenze hier ist 3, zählen wir auch die Eingabe der Grafik, so ist das richtige Ergebnis 21, weil: 2-> 8-> 11.
Wenn wir Grenze von 4 hätte Schritte wäre das Ergebnis 31 sein: 2-> 10-> 8-> 11
Mein Freund es mit DFS zu tun versucht, ist er recht? Was ist der beste Algorithmus?

Answer 1

Gute Antwort ist die gleichzeitige Verwendung mehrerer Routen. ich meinen wir mit 2-Längengrenze gehen könnte:

• 1 links 0 rechts
• 0 links 2 rechts

Arbeiten, aber etwas langsam, Code 1 rechts nach links:) Seine Arbeitszeit ist 28s, während andere Lösungen mit 2s gehen können (10 Tests nicht bekannt)

int mSum(Node* node, int mvLeft) { 
    mvLeft--; 
    if (mvLeft < 0) { 
     return 0; 
    } 
    else if (mvLeft == 0) { 
     return node->value; 
    } 

    if (node->left != nullptr && node->right != nullptr) { 
     int max = 0; 
     for (int i = 0; i <= mvLeft; i++) { 
      max = Max(max, mSum(node->left, i) + mSum(node->right, mvLeft - i)); 
     } 
     return max + node->value; 
    } 
    else if (node->left != nullptr) { 
     return mSum(node->left, mvLeft) + node->value; 
    } 
    else if (node->right != nullptr) { 
     return mSum(node->right, mvLeft) + node->value; 
    } 
    return node->value; 
}