我需要關于我正在尋找從葉子到葉子的不相交路徑的任務的建議（它們不能沿著相同的路徑/邊緣回傳），以便它們的總和創造最大可能的值，即路徑不能相交并且必須是盡可能的好屬于總。請注意，路徑中斷的點（根）不包括在總和中，即。圖片。
我根本不知道如何解決這個問題。我附上了試圖決定是選擇一片葉子的路徑還是選擇較小的子樹的代碼，但它不能正常作業。
如果有人有任何學習材料，我將非常感激。提前謝謝所有程式
我無法創建一個演算法來解決這個問題。我想要一些可以在解決方案中使用的建議和學習材料。
uj5u.com熱心網友回復：
讓我們呼叫函式，f我們的整體任務，輸入引數為樹的根。讓我們呼叫函式 ，g從給定節點（包括該節點）的最大連續下降路徑，它還f為每個未選擇的節點添加結果。
從樹的根開始，在 的運行中f，對于每個節點，我們可以將其（1）指定為路徑中的父節點，或者（2）不屬于任何路徑。在 (1) 的情況下，我們希望g(left_child) g(right_child). 在 (2) 的情況下，我們希望f(left_child) f(right_child).
帶有第二個示例的 Python 代碼，其中根不是任何路徑的一部分：
def g(tree):
if tree == None:
return 0
return tree["val"] max(
g(tree["l"]) f(tree["r"]),
g(tree["r"]) f(tree["l"])
)
def f(tree):
if tree == None:
return 0
return max(
g(tree["l"]) g(tree["r"]),
f(tree["l"]) f(tree["r"])
)
tree = {
"val": 0,
"l": {
"val": 2,
"l": {
"val": 2,
"l": None,
"r": None
},
"r": {
"val": 3,
"l": None,
"r": None
}
},
"r": {
"val": 1,
"l": {
"val": 2,
"l": None,
"r": None
},
"r": {
"val": 3,
"l": None,
"r": None
}
}
}
print(f(tree)) # 10
你的第三個例子：
tree = {
"val": 0,
"l": {
"val": 6,
"l": {
"val": 5,
"l": None,
"r": None
},
"r": {
"val": 3,
"l": None,
"r": None
}
},
"r": {
"val": 5,
"l": {
"val": 7,
"l": {
"val": 3,
"l": None,
"r": None
},
"r": {
"val": 6,
"l": None,
"r": None
}
},
"r": {
"val": 7,
"l": {
"val": 6,
"l": None,
"r": None
},
"r": {
"val": 7,
"l": None,
"r": None
}
}
}
}
print(f(tree)) # 42
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/523495.html
下一篇：邏輯數學運算