在一群朋友中，除了一個朋友之外，每個人都在監視另一個朋友。每個朋友都有一些貴重物品，這是一個正整數。找到一組擁有最多貴重物品的朋友，這樣任何朋友都不會窺探該組中的任何其他朋友。
示例：對于可能的測驗用例之一，我們有下圖。每個頂點上方的值是它們所擁有的貴重物品的正數。
最好的可能組是 [A,F,D,J,H] = 92 值
看起來我們可以通過忽略遍歷圖并計算所有可能組的組合來實作解決方案。不幸的是，無法想到動態編程方法或如何開始。
uj5u.com熱心網友回復：
給出圖表上的約束，您將始終擁有：
- 一個不相交的連通子圖，它是一棵由零個或多個簡單路徑組成的樹，所有路徑都從沒有監視任何人的朋友分支；和
- 零個或多個不相交的連接子圖，其中每個子圖恰好包含一個回圈和零個或多個從回圈分支的簡單路徑。
為了獲得最好的貴重物品：
- 在每個分支路徑內，每個選定頂點之間最多可以有兩個未選定頂點。（如果有三個未選擇的頂點，那么如果選擇這三個頂點的中間頂點，您會得到更好的結果；即，選擇的頂點
(A)->B->C->D->(E)在哪里()總是會給出更好的結果(A)->B->(C)->D->(E)）。 - 在每個回圈中，除非在分支路徑中被選定的相鄰頂點阻擋，否則每個選定頂點之間最多可以有兩個未選定頂點。（出于與分支路徑類似的原因）。
如果您有連接的子圖（類似于示例的底部，但Esies I，而不是什么都不做）：
-----------
V |
C -> D -> E -> I -> J <- H
然后，您可以從回圈開始并向外作業到分支路徑或從分支路徑向內作業。如果您考慮向外回圈，則：
- 如果
E選擇 thenD，I并且J不能是 并且假設達到了 1 的最小間隔，那么C并且H必須選擇。 - if
I被選中 thenEandJ不能被選中 andHand eitherCorD可以被選中。 - if
J被選中 thenE，I并且H不能被選中，并且要么 要么C可以D被選中。 - 如果沒有選擇回圈中的任何頂點，則選擇
H其中一個C或D可以選擇（在這種情況下，這始終是一個比選擇更糟糕的選擇J，因為它不會阻止來自分支路徑的選擇）。
這為以下連接的子圖提供了可能的解決方案：
- C、E、H
- C、我、H
- D、我、H
- C，J
- D，J
您可以對每個不相交的子圖執行類似的操作，并且對于包含未監視任何人的朋友的一個不相交的子圖，可以選擇或不選擇該朋友，并且可以獨立評估每個分支簡單路徑，選擇跳過選定頂點之間的一兩個頂點并找到最佳總數。
為子圖找到具有最高值的解決方案，然后轉到下一個子圖。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/532369.html
標籤：算法动态规划图论
下一篇：合并串列項的優化方案