ブランチとバインドされたナップザックに含まれるアイテムの計算

Question

ブランチとバインドされたアルゴリズムを使用して、与えられたアイテムのセットから最適な利益を評価しましたが、今度はこの最適なソリューションに含まれるアイテムを見つけたいと思います。次のように私は（hereから適応）最適なナップザックの利益の価値を評価しています：

import Queue 

class Node: 
    def __init__(self, level, profit, weight): 
     self.level = level # The level within the tree (depth) 
     self.profit = profit # The total profit 
     self.weight = weight # The total weight 

def solveKnapsack(weights, profits, knapsackSize): 
    numItems = len(weights) 
    queue = Queue.Queue() 
    root = Node(-1, 0, 0)  
    queue.put(root) 

    maxProfit = 0 
    bound = 0 
    while not queue.empty(): 
     v = queue.get() # Get the next item on the queue 

     uLevel = v.level + 1 
     u = Node(uLevel, v.profit + e[uLevel][1], v.weight + e[uLevel][0]) 

     bound = getBound(u, numItems, knapsackSize, weights, profits) 

     if u.weight <= knapsackSize and u.profit > maxProfit: 
      maxProfit = uProfit 

     if bound > maxProfit:  
      queue.put(u) 

     u = Node(uLevel, v.profit, v.weight) 
     bound = getBound(u, numItems, knapsackSize, weights, profits) 

     if (bound > maxProfit): 
      queue.put(u) 
    return maxProfit 

# This is essentially the brute force solution to the fractional knapsack 
def getBound(u, numItems, knapsackSize, weight, profit): 
    if u.weight >= knapsackSize: return 0 
    else: 
     upperBound = u.profit 
     totalWeight = u.weight 
     j = u.level + 1 
     while j < numItems and totalWeight + weight[j] <= C: 
      upperBound += profit[j] 
      totalWeight += weights[j] 
      j += 1 
     if j < numItems: 
      result += (C - totalWeight) * profit[j]/weight[j] 
     return upperBound 

ので、はどのように私は最適解、だけではなく、利益を形成するアイテムを得ることができますか？

Answer 1

私はこれについてしばらく考えていました。どうやら、Nodeクラス内にnode_pathを割り当て、現在のレベルを追加するメソッドをいくつか追加する必要があります。あなたのループの中であなたのメソッドを呼び出し、node_weightが容量よりも小さく、その値がmax_profitより大きい、つまりmaxProfitを割り当てる場所にあるときに、あなたのoptimal_item_listにpath_listを割り当てます。あなたはjava実装を見つけることができますhere

Answer 2

私はこれをあなたのコードを出発点として使っています。私はその後、ソルバー同様に、私のナップサックを始めたが、root = Node(0, 0, 0, 0.0, [])をinitalized

class Node: 
    def __init__(self, level, profit, weight, bound, contains): 
     self.level = level   # current level of our node 
     self.profit = profit 
     self.weight = weight   
     self.bound = bound   # max (optimistic) value our node can take 
     self.contains = contains # list of items our node contains 

：私は私のようNodeクラスを定義しました。値root.boundは浮動小数点である可能性があります。これは0.0に初期化しましたが、他の値は（少なくとも私の問題では）すべて整数です。ノードにはこれまで何も含まれていないので、私は空のリストでそれを開始しました。私だけでcontainsリストを更新

u.contains = v.contains[:] # copies the items in the list, not the list location 
# Initialize u as Node(uLevel, uProfit, uWeight, 0.0, uContains) 
u.contains.append(uLevel) # add the current item index to the list 

を注：私は、私は（これは必要だったかわからない）各ノードにバインドされ、containsリストを更新使用して保存されたことを除いて、あなたのコードに似た輪郭線をたどっ「アイテムを取る」ノード。これは、最初のif bound > maxProfit:ステートメントの前に、メインループの最初の初期化です。あなたがmaxProfitの値を更新したとき、私は、右のこの前if:文でcontainsリストを更新：

if u.weight <= knapsackSize and u.value > maxProfit: 
    maxProfit = u.profit 
    bestList = u.contains 

これは、あなたがbestListに取っている項目のインデックスを格納します。私はまた、v = queue.get()の直後のメインループに条件if v.bound > maxProfit and v.level < items-1を追加したので、最後の項目に到達しても続かないようにしました。私は探検する価値のないブランチをループしません。

あなたはアイテムがインデックスによって選択されたバイナリのリスト出力上映を取得したい場合にも、あなたが使用できます。

taken = [0]*numItems 
for item in bestList: 
    taken[item] = 1 

print str(taken) 

私は私のコードでは他のいくつかの違いがあったが、これは取得することができます必要がありますあなたの選択したアイテムリストを出してください。