動態規劃：在n個節點的路徑中可能的最大重量

Question

首先，我想說這是我的第一個關於Stack Overflow的問題，如果我的問題沒有被問到，或者如果這個問題是不應該的，不要問，請告訴我，所以我可以解決它（我已經閱讀了導遊已經，但你永遠不知道！）

因此，讓我們開始：我試圖做一個有針對性的非循環算法和加權圖表（重量可以是負值或正值）。該算法必須從特定節點開始尋找具有最大權重的路徑，並且該路徑可以通過最多N個節點（如果它將獲得更好的權重，則可以使用更少的節點）。

我明白我將不得不使用動態編程來做到這一點，但我不知道如何做到這一點。我已經做了相當多的研究，並且我只提出了「從節點u到節點v的最長路徑算法」，但這不是我想要實現的。

我對Dijkstra的算法很熟悉，但我不認爲這是我應該使用的。

非常感謝您閱讀我，並提前感謝您的幫助。

Answer 1

輸入訴算法，Z：

1. 緊密關聯組件，知道你有沒有從節點U的方式裏面正權重週期可以返回無限

2. 排序定向使用圖形DFS從葉子節點

3. 啓動並返回最大（weight_of_node（leave1，Z），......）

4. 爲當前節點打印並選擇最重的父節點通過遞歸函數計算。如果節點只有一個父親挑這個父親，如果節點爲v返回V的重量和打印

5. 現在所有選定的節點都印

*當你計算的重量節點

`weight_of_node（X，Z）：

如果這些z- == 0

return - infinite 

return maximum（weight_of_node（father_node1），weight_of_node（father_node2），...）+ current_node_weight`，z-1）