跟蹤在二叉決策樹中導致目標結果的節點序列？

我已經在Python中實現了一個二叉決策樹來解決一個相當標準的揹包問題：存在一個對象集合，每個對象都有一個相關的權重和值，並且必須選擇對象以使值最大化，並受到權重約束。跟蹤在二叉決策樹中導致目標結果的節點序列？

我看到如何返回最大值，但我正努力尋找一種聰明的方式來返回產生最大值的對象的身份。

現在，我正在創建一個「字符串向量」，可以說，「1」和「0」代表打包或不打包特定對象的選擇。字符串向量中的第一個「1」或「0」表示對與對象列表中的第一個對象相對應的對象作出的決定，依此類推。

有沒有更好的方法來做到這一點？

我寫的代碼：

def knapsack(weightList, valueList, availableWeight, index): 
    if index == 0: 
     if weightList[index] <= availableWeight: 
      return valueList[index], '1' 
     else: 
      return 0, '0' 
    else: 
     reject, rVector = knapsack(weightList, valueList, availableWeight, index - 1) 
     rVector += "0" 
     if weightList[index] <= availableWeight: 
      take, tVector = knapsack(weightList, valueList, availableWeight - weightList[index], index - 1) 
      take += valueList[index] 
      tVector += "1" 
     else: 
      take = -1 

     if take > reject: 
      return take, tVector 
     else: 
      return reject, rVector 

weightList = [1, 2, 6, 5, 8, 3, 7, 2, 4, 7, 1] 
valueList = [2, 5, 4, 6, 7, 8, 2, 4, 5, 6, 8] 
availableWeight = 5 
index = len(weightList) - 1 

maxValue, vector = knapsack(weightList, valueList, availableWeight, index) 
print maxValue 
print vector

輸出是：

18 
10000100001

來源

2012-09-16 Ryan

如果字符串結束了主要包含「0」與幾個「1」，那麼它的好多了返回一個Python集合對象。一旦你得到了結果作爲一個集合，它仍然可以讓你有效地決定索引是否在集合中 - 這樣，首先使用一串標誌幾乎沒有什麼優勢。

請注意，集合是可變的，如果在算法中執行不正確，可能會造成混淆。我會建議在'set'上選擇'frozenset'。

來源

2012-09-17 09:42:26

跟蹤在二叉決策樹中導致目標結果的節點序列？

回答

相關問題