0/1 Knapsack Problem

+10

Você tem n itens. O item i pesa weights[i] e vale values[i]. Sua mochila comporta um peso total de, no máximo, capacity. Há apenas uma unidade de cada item, e você pode colocá-lo inteiro na mochila ou deixá-lo para trás. Retorne o maior valor total que você pode levar.

Função

knapsack(weights: integer-array, values: integer-array, capacity: integer) → integer

weightsinteger-array: o peso de cada item
valuesinteger-array: o valor de cada item
capacityinteger: o maior peso que a bolsa pode carregar
Retornainteger: o maior valor total de itens cujos pesos cabem na capacidade

Restrições

1 ≤ n ≤ 100, em que n = weights.length = values.length
1 ≤ weights[i] ≤ 1000
1 ≤ values[i] ≤ 10⁴
1 ≤ capacity ≤ 1000

Exemplos

Entrada: weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
Saída: 17
Explicação: Os itens 0 e 2 pesam 4 + 3 = 7 e valem 10 + 7 = 17. Colocar primeiro o item mais valioso (peso 5, valor 12) deixa espaço apenas para o item 1, totalizando 16.

Para ir além

Suponha que a capacidade possa chegar a 10^9, enquanto a soma dos valores seja de, no máximo, 10^4. Pelo que você indexaria a tabela?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Nenhuma ordem gulosa funciona: colocar primeiro o item mais valioso resulta em 16, não 17, no primeiro exemplo. O melhor valor a partir do item i depende apenas de i e do espaço restante, um número inteiro de até 1000. Uma célula da tabela por par resulta em O(n × capacity), e uma linha é suficiente se você percorrer as capacidades em ordem decrescente.

Tente as duas opções para cada item

Correta, mas não termina nos maiores testes

Intuição

Seja best(i, room) o maior valor que os itens de i em diante podem adicionar com room unidades livres; após o último item, esse valor é 0. Ignorar o item i resulta em best(i+1, room). Colocá-lo na mochila, quando weights[i] ≤ room, resulta em values[i] + best(i+1, room-weights[i]). Fique com o maior valor. Cada combinação de itens que cabe corresponde a uma sequência de escolhas entre colocar na mochila e ignorar, e a recursão tenta todas elas.

Cada item dobra o número de caminhos. Quando todos os 100 itens cabem juntos, como no caso de itens com peso 10 cada em uma mochila de capacidade 1000, são 2^100 caminhos.

Algoritmo

Escreva best(i, room); retorne 0 quando i passar do último item.
Defina skip como best(i+1, room).
Se weights[i] > room, retorne skip.
Caso contrário, retorne o maior entre skip e values[i] + best(i+1, room-weights[i]).
Retorne best(0, capacity).

def knapsack(weights, values, capacity):
    n = len(weights)

    # The most value items i, i+1, ... can add with room units of weight left
    def best(i, room):
        if i == n:
            return 0
        skip = best(i + 1, room)
        if weights[i] > room:
            return skip
        take = values[i] + best(i + 1, room - weights[i])
        return max(skip, take)

    return best(0, capacity)

Preencha uma tabela por item e capacidade

Intuição

A recursão alcança o mesmo par (i, room) por muitos caminhos. Há no máximo 101 × 1001, cerca de 10^5, pares, então calcule cada um apenas uma vez.

Seja best[i][c] o maior valor que os primeiros i itens podem colocar em uma mochila de capacidade c; a linha 0 é toda 0. Para o item i-1, com peso w e valor v, deixá-lo de fora resulta em best[i-1][c] e, ao colocá-lo na mochila, quando w ≤ c, resulta em best[i-1][c-w] + v. A linha i consulta apenas a linha i-1, então cada item entra em uma célula no máximo uma vez.

No primeiro exemplo, o item 2 (peso 3, valor 7) eleva a capacidade 7 para best[2][4] + 7 = 17. O item 3 então oferece apenas best[3][2] + 12 = 16, então a resposta continua sendo 17.

Algoritmo

Crie uma tabela com n+1 linhas e capacity+1 colunas, todas com 0.
Para cada linha i de 1 a n, use w = weights[i-1] e v = values[i-1].
Para cada capacidade c, defina best[i][c] como best[i-1][c].
Se w ≤ c e best[i-1][c-w] + v for maior, armazene esse valor.
Retorne best[n][capacity].

def knapsack(weights, values, capacity):
    n = len(weights)
    # best[i][c]: the most value from the first i items within capacity c
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            best[i][c] = best[i - 1][c]  # leave item i-1 out
            if w <= c and best[i - 1][c - w] + v > best[i][c]:
                best[i][c] = best[i - 1][c - w] + v  # put it in
    return best[n][capacity]

Uma linha, capacidades percorridas em ordem decrescente

Intuição

A linha i precisa apenas da linha i-1, então mantenha uma linha best[c] e sobrescreva-a item por item. A direção da iteração determina se a resposta está correta.

Ao percorrer c em ordem crescente, best[c-w] talvez já inclua o item atual. Um item de peso 3 e valor 5, com capacidade 6, faz a capacidade 3 valer 5; então a capacidade 6 lê esse valor e passa a valer 10: duas cópias. Ao percorrer de capacity até w em ordem decrescente, a célula que você lê fica abaixo da que você escreve e será sobrescrita depois, então ela ainda contém o valor da linha anterior.

A iteração em ordem crescente é o loop correto quando os itens podem ser usados um número ilimitado de vezes. Aqui, o tempo continua sendo O(n × capacity) e a memória cai para uma linha.

Algoritmo

Crie best com capacity + 1 entradas, todas com 0.
Para cada item com peso w e valor v, percorra c de capacity até w.
Se best[c-w] + v superar best[c], armazene esse valor em best[c].
Retorne best[capacity].

def knapsack(weights, values, capacity):
    # best[c]: the most value from the items seen so far within capacity c
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        # Walk the capacities downward so each item goes in at most once
        for c in range(capacity, w - 1, -1):
            if best[c - w] + v > best[c]:
                best[c] = best[c - w] + v
    return best[capacity]

Armadilhas e casos extremos

Percorrer as capacidades em ordem crescente na versão de uma única linha faz com que um item seja contado duas vezes: um item de peso 3 e valor 5 em uma mochila de capacidade 6 soma 10 em vez de 5.
Uma linha com capacity entradas em vez de capacity + 1. Retornar best[capacity-1] faz com que qualquer preenchimento exato da mochila seja perdido, como um item de peso 1 em uma mochila de capacidade 1.
Iniciar as entradas com menos infinito. A mochila não precisa estar cheia, então todas as entradas começam em 0; com menos infinito, o terceiro exemplo retorna menos infinito em vez de 0.
Um item mais pesado que a mochila deve ser ignorado. No terceiro exemplo, um intervalo fechado w...capacity interrompe o programa em Swift, e (w+1):(capacity+1) conta de trás para frente em R.

Perguntas frequentes3

Qual é a complexidade de tempo do problema da mochila 0/1?

A tabela é executada em tempo O(n × capacity), cerca de 10^5 etapas para 100 itens e uma capacidade de 1000, e a versão de uma linha usa memória O(capacity). O limite é pseudopolinomial: cresce com o valor da capacidade, não com o número de dígitos. O problema geral é NP-difícil.

Por que um algoritmo guloso não funciona para o problema da mochila 0/1?

Uma regra gulosa nunca desfaz uma escolha, mesmo quando o item deixa espaço que nada ocupa. Com capacidade 7, o item de peso 5 e valor 10 empata na melhor proporção, mas os itens de peso 4 e 3 juntos valem 13. A estratégia gulosa pela proporção é ótima apenas para a mochila fracionária, na qual você pode dividir os itens.

Como descobrir quais itens a mochila 0/1 escolheu?

Mantenha a tabela completa e percorra-a de trás para frente a partir de best[n][capacity]. Se best[i][c] for diferente de best[i-1][c], o item i-1 foi colocado na mochila; portanto, registre-o e subtraia seu peso de c. Caso contrário, vá para a linha i-1 com o mesmo c.

def knapsack(weights, values, capacity):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

weights = [4, 2, 3, 5]
values = [10, 4, 7, 12]
capacity = 7

Saída Esperada

0/1 Knapsack Problem

Função

Restrições

Exemplos

Dicas

Solução

Tente as duas opções para cada item

Preencha uma tabela por item e capacidade

Uma linha, capacidades percorridas em ordem decrescente

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos