knapsack

(imagem retirada daqui)

Problema

Dado uma lista de itens, na qual cada item possui um valor e peso, qual a maior soma de valores que eu posso carregar em minha mochila sem ultrapassar meu peso máximo?

Formulando

// Um item de valor 3 e peso 5
const item = { v: 3, p: 5 }

// Lista de itens:
const items = [
    { v: 3, p: 5 },
    { v: 4, p: 4 },
    { v: 1, p: 2 }
]

// Peso máximo suportado pela minha mochila
const pesoMaximo = 7

// Nesse exemplo
knapsack(items, pesoMaximo) // O resultado seria 5

Solução

Quando pensamos em uma solução, naturalmente diversas possibilidades aparecem:

E se eu ordenar essa lista pelos maiores valores?

Ou talvez pelos menores pesos!

Quem sabe remover os “piores” itens e trabalhar só com os demais?

Por que eu estou lendo isso mesmo? <abre Netflix>

Propor diversas possíveis soluções é algo bom, estamos experimentando, mas infelizmente nenhuma dessas frases acima vai ajudar.

A solução é muito simples de ser escrita, mas talvez um pouco complicada de ser compreendida: basta tentar todas as possibilidades, simulando todos os cenários nos quais um item pode ou não estar na mochila.

Continue lendo abaixo para montarmos uma implementação dessa solução bem bonita, ou senão clique aqui :)

Implementação

Vamos resolver o seguinte cenário de teste:

const items = [
    { v: 3, p: 5 },   // 1
    { v: 4, p: 4 },   // 2
    { v: 1, p: 2 }    // 3
]

const pesoMaximo = 7

Vamos simular um primeiro cenário:

Ação Mochila (cenário 1)
Nenhuma, mochila vazia []
(v: 0)
(p: 7)
Verifico se item 1 cabe []
(v: 0)
(p: 7)
Coloco o item 1 [{v: 3, p: 5}]
(v: 3)
(p: 2)
Verifico se item 2 cabe [{v: 3, p: 5}]
(v: 3)
(p: 2)
Item 2 excede limite peso [{v: 3, p: 5}]
(v: 3)
(p: 2)
Verifico se item 3 cabe [{v: 3, p: 5}]
(v: 3)
(p: 2)
Coloco o item 3 [{v: 3, p: 5},
{v: 1, p: 2}]
(v: 4)
(p: 0)
Fim Meu resultado é 4 (sobrou 0 de peso)

A lógica é a seguinte: em cada passo, verificar se o próximo item cabe na mochila, então iniciar um novo cenário INCLUINDO e outro EXCLUINDO o item.

Código

A função recursiva:

function knapsack_r(items, maximoPeso, i) {

    // Se terminaram os itens, o valor desse passo é 0
    if (i >= items.length)
        return 0

    // Se o item é muito pesado, segue sem ele
    if (maximoPeso - items[i].p < 0)
        return knapsack_r(items, maximoPeso, i + 1)

    /*
        Quero o maior valor desses dois cenários:
        - Incluindo o item (subtraindo peso e adicionando valor)
        - Excluindo o item (peso e valores inalterados)
    */
    return Math.max(
        knapsack_r(items, maximoPeso - items[i].p, i + 1) + items[i].v,
        knapsack_r(items, maximoPeso, i + 1)
    )
}

A mágica está na lógica recursiva aplicada para todos os itens, todos os cenários possíveis são testados, e retornamos sempre o maior.

Precisamos também de uma funçãozinha auxiliar apenas para iniciar a recursão no index 0:

function knapsack(items, maximoPeso) {
    return knapsack_r(items, maximoPeso, 0)
}

Utilizando nosso monstrinho de Inceptions:

const pesoMaximo = 7
const items = [
    { v: 3, p: 5 },
    { v: 4, p: 4 },
    { v: 1, p: 2 }
]

knapsack(items, pesoMaximo) // 5

Complexidade

Para determinar a complexidade de tempo, podemos fazer alguns testes de quantas possibilidades temos com determinada quantidade de itens:

Lista com Possibilidades
nenhum item 1 (vazia)
{}
1 item 2 (vazia ou 1 item)
{}
{1}
2 itens 4
{}
{1}
{2}
{1, 2}
3 itens 8
{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}

Não é necessário continuar para percebermos que o número de combinações segue a potência do 2.

Logo, a complexidade de tempo dessa implementação é O().

Fazendo melhor

Como podemos ver, nossa implementação acima se comporta como O() e você deve estar se perguntado: um algoritmo de complexidade quadrática é utilizado na prática?

Pois é: não!

Como estamos fazendo uma recursão, nesse caso é possível aplicar programação dinâmica, que seria a recursão com uma tabela, ou, aproveitar os valores já calculados para evitar reprocessamento.

Veja como transformar a versão recursiva em dinâmica nesse excelente vídeo!

Finalizando

Espero que você tenha gostado de aprender sobre esse problema muito comum em campeonatos e entrevistas de programação.

A base para esse post foi derivada do ótimo site de problemas de computação ByteByByte.

Até a próxima.