我正在處理一個問題，該問題已概括為我在標題中描述的內容。本質上，我有一個 DAG，它看起來像這樣：（我知道 DAG 的樣子并不重要，我只是認為它可能會顯示我的位置）。
我已將頂點值繪制為與圖層中頂點的邊緣距離（或成本），其中圖層由垂直對齊的頂點組成。換句話說，當 a 和 b 在同一“層”中時，邊 (a,a') (b,a') 具有相等的值。
我需要找到從最左邊層到最右邊層的路徑，使得路徑中邊的值之和等于或小于并盡可能接近目標值。
最初的問題基本上是在不同矩陣中找到等于（或小于并盡可能接近）目標值的單個值的總和，其中使用每個值中的一個值。
我必須使用制表，我不知道如何解決這個問題。我不是在尋找完整的解決方案。如果這個問題寫得不好，請告訴我。
uj5u.com熱心網友回復：
- 從每一層取最小成本節點以獲得最小成本路徑
- 從每一層取最大成本節點以獲得最大成本路徑
- 如果目標超出最小值和最大值之間的范圍，則完成
- 使最小路徑成為當前路徑
- 從同一層路徑中的節點中選擇具有最大正增量的節點，但與當前路徑中的節點交換時，該節點不會使路徑成本超過目標。交換。
- 重復最后一步，直到沒有更多的交換是可能的。
uj5u.com熱心網友回復：
首先，我將評論您的原始問題公式“給定 n 組整數和系結 B，從每組中選擇一個數字以實作最大總和 <= B”比 DAG 路徑類比要簡單得多，所以我會堅持的。
不幸的是，這個問題是 NP-Hard 通過減少子集總和：給定一個子集總和的實體與宇宙S = (s1, s2, ... sn)和目標 B，用 n 個大小為 2 的集合創建你的問題的一個實體：(s1, 0), (s2, 0), ... (sn, 0)。當存在等于 B 的子集和時，邊界 B 是可達的。
幸運的是，如果您的值都很小，您可以使用類似于子集求和演算法的偽多項式演算法：
- 初始化一個長度為 (B 1) 的布爾陣列 A 和除 A[0] = True 之外的所有值都為 false
- 對于集合串列中的每個集合 S：
初始化一個長度為 (B 1) 的新布爾陣列 A'，所有值都為 False。
對于 S 中的每個數字 x：
- 對于 A[i] = True 的每個索引 i：如果在范圍內，則設定 A'[i x] = True。
交換 A 和 A'。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/346254.html
上一篇：python將引數附加到函式呼叫