0-1 рюкзак 2 ряда как найти элементы

Question

После урока здесь
Я реализовал рабочий алгоритм ранца 0-1, используя только две строки.
Что выводит правильное конечное значение.
Имена содержат идентификатор каждого элемента, который используется.

def KnapSack(val, wt, n, W): 
    names = n
    n = len(n)
    mat = [[0 for i in range(W + 1)] for i in range(2)] 

    i = 0
    while i < n: 
        j = 0 

        if i % 2 == 0: 
            while j < W:
                j += 1
                if wt[i] <= j:
                    mat[1][j] = max(val[i] + mat[0][j - wt[i]], mat[0][j]) 
                else:
                    mat[1][j] = mat[0][j] 
        else: 
            while j < W: 
                j += 1
                if wt[i] <= j: 
                    mat[0][j] = max(val[i] + mat[1][j - wt[i]], mat[1][j]) 
                else: 
                    mat[0][j] = mat[1][j] 
        i += 1
    if n % 2 == 0: 
        return mat[0][W] 
    else: 
        return mat[1][W] 

Основываясь на этом коде, как я смогу вывести элементы, используемые для создания правильного значения ранца?Например, конечный результат равен 54, мне нужно найти, какие элементы, добавленные вместе, получают значение 54.

Answer 1

Как и в случае с обычным рюкзаком, вам придется отслеживать, как вы попали в это конкретное состояние в массиве DP.Таким образом, в вашей таблице mat вместо отслеживания полученной суммы мы также собираемся отслеживать элементы, которые ее составляют - теперь каждая запись в таблице является кортежем с суммой и списком имен.

Iтакже позволил себе сделать один критический рефакторинг в вашем коде - видите ли вы, как выглядят похожие пункты if и else вашего кода?Мы можем объединить их, основывая нашу логику на i % 2 - в моем коде это cur.Это позволяет нам писать только логику - это довольно распространенный трюк для ранца 0-1.В общем случае, по возможности, следует избегать вставки копий, поскольку это часто является источником ошибок.Без, в дальнейшем, вот код:

def KnapSack(val, wt, n, W): 
    names = n
    n = len(n)
    mat = [[(0, []) for i in range(W + 1)] for i in range(2)] 

    i = 0
    while i < n: 
        j = 0 
        cur = i % 2

        while j < W:
            j += 1
            if wt[i] <= j:
                if val[i] + mat[cur][j - wt[i]][0] > mat[cur][j][0]:
                    mat[1 - cur][j] = (val[i] + mat[cur][j - wt[i]][0], mat[cur][j - wt[i]][1][:] + [names[i]])
                else:
                    mat[1 - cur][j] = (mat[cur][j][0], mat[cur][j][1][:])
            else:
                mat[1 - cur][j] = (mat[cur][j][0], mat[cur][j][1][:]) 

        i += 1
    if n % 2 == 0: 
        return mat[0][W] 
    else: 
        return mat[1][W] 

print(KnapSack([7, 8, 4], [3, 8, 6], ['apple', 'box', 'peach'], 10))

печатает (11, ['apple', 'peach']), так как 11 является лучшим значением, составленным из первого и третьего элементов.

Обратите внимание на дополнительные [:]чтобы сделать копии списка - списки не копируются глубоко, что могло бы испортить наше решение, так как мы будем постоянно менять этот список снова и снова.

Удачи в учебе!