Подсчет предметов, входящих в ветку и связанный рюкзак

Question

Используя алгоритм ветвей и границ, я оценил оптимальную прибыль от данного набора предметов, но теперь я хочу выяснить, какие предметы включены в это оптимальное решение. Я оцениваю значение прибыли оптимального ранца следующим образом (адаптировано отсюда):

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 Класс как:

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

Затем я запустил свой рюкзак Solver аналогичным образом, но инициализировал root = Node(0, 0, 0, 0.0, []), Значение 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: заявление. Я обновил contains список в if: заявление прямо перед этим, когда вы обновляете значение maxProfit:

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

Здесь хранятся индексы предметов, которые вы принимаете bestList, Я также добавил условие if v.bound > maxProfit and v.level < items-1 в основной цикл сразу после v = queue.get() так что я не продолжаю идти после того, как достигну последнего пункта, и я не перебираю ветки, которые не стоит изучать.

Также, если вы хотите получить вывод в двоичном списке, показывающий, какие элементы выбраны по индексу, вы можете использовать:

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

print str(taken)

У меня были некоторые другие отличия в моем коде, но это должно позволить вам получить список выбранных вами предметов.

Answer 2

Я думал об этом в течение некоторого времени. Очевидно, вам нужно добавить несколько методов в ваш класс Node, которые будут назначать путь_узла и добавлять к нему текущий уровень. Вы вызываете ваши методы внутри вашего цикла и назначаете path_list для вашего optim_item_list, когда ваш node_weight меньше емкости, а его значение больше, чем max_profit, то есть где вы назначаете maxProfit. Вы можете найти реализацию Java здесь