Tính toán các hạng mục được bao gồm trong chi nhánh và lô hàng bị ràng buộc

Question

Sử dụng thuật toán nhánh và liên kết Tôi đã đánh giá lợi nhuận tối ưu từ một tập hợp các mặt hàng nhất định, nhưng bây giờ tôi muốn tìm hiểu các mặt hàng nào được bao gồm trong giải pháp tối ưu này. Tôi đánh giá giá trị lợi nhuận của ba lô tối ưu như sau (chuyển thể từ 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 

Vì vậy, thế nào tôi có thể nhận được vật phẩm hình thành giải pháp tối ưu, chứ không phải chỉ là lợi nhuận?

Answer 1

Tôi đã suy nghĩ về điều này một thời gian. Rõ ràng, bạn phải thêm một số phương thức bên trong lớp Node của bạn để gán node_path và thêm mức hiện tại vào nó. Bạn gọi các phương thức của bạn bên trong vòng lặp của bạn và gán path_list cho tệp tối ưu__khi của bạn khi node_weight của bạn nhỏ hơn dung lượng và giá trị của nó lớn hơn max_profit, nghĩa là bạn gán maxProfit. Bạn có thể tìm thấy triển khai java here

Answer 2

Tôi làm việc này bằng cách sử dụng mã của bạn làm điểm xuất phát. Tôi định nghĩa lớp Node tôi như:

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 

Sau đó tôi bắt đầu ba lô của tôi giải tương tự, nhưng initalized root = Node(0, 0, 0, 0.0, []). Giá trị root.bound có thể là một phao, đó là lý do tại sao tôi initalized nó để 0.0, trong khi các giá trị khác (ít nhất là trong vấn đề của tôi) là tất cả các số nguyên. Các nút không chứa gì cho đến nay, vì vậy tôi bắt đầu nó với một danh sách trống. Tôi đi theo một phác thảo tương tự như mã của bạn, ngoại trừ việc tôi lưu trữ các ràng buộc trong mỗi nút (không chắc chắn này là cần thiết), và cập nhật danh sách contains sử dụng:

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 

Lưu ý rằng tôi chỉ cập nhật danh sách contains trong nút "lấy mục". Đây là lần khởi tạo đầu tiên trong vòng lặp chính của bạn, trước câu lệnh if bound > maxProfit: đầu tiên. Tôi cập nhật danh sách contains trong báo cáo if: ngay trước này, khi bạn cập nhật giá trị của maxProfit:

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

này lưu trữ các chỉ số của các mục mà bạn đang dùng để bestList. Tôi cũng đã thêm điều kiện if v.bound > maxProfit and v.level < items-1 vào vòng lặp chính ngay sau v = queue.get() để tôi không tiếp tục đi sau khi tôi đến mục cuối cùng và tôi không lặp qua các nhánh không đáng khám phá.

Ngoài ra, nếu bạn muốn có được một danh sách kết quả hiển thị nhị phân mà mục được lựa chọn bởi chỉ mục, bạn có thể sử dụng:

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

print str(taken) 

tôi đã có một số khác biệt khác trong mã của tôi, nhưng điều này nên cho phép bạn để có được danh sách mục đã chọn của bạn.