Programação Dinâmica 2 - Problema da Mochilha (Knapsack)

Escrito por Luca Dantas

Nesta aula, iremos abordar algumas variações de um problemas clássico de programação dinâmica e diferentes maneiras de abordá-lo.

Problema da mochila (Knapsack)

Enunciado:

Existe um conjunto de $n$ elementos, e para todo $1 \leq i \leq n$, o elemento $i$ possui peso $p_i$ e valor $v_i$. Queremos escolher alguns desses itens para levar para casa. Para auxiliar na tarefa temos uma mochila com capacidade $C$, ou seja a soma dos pessos dos itens que escolhermos tem que ser menor ou igual ($\leq$) a $C$. Porém, como sabemos os valores (assim como os pesos) de cada item, queremos escolher um conjunto de itens tal que a soma dos valores seja máxima.

Restrições:

Todos os valores dados são inteiros
$1 \leq n \leq 100$
$1 \leq C \leq 10^5$
$1 \leq p_i \leq C$
$1 \leq v_i \leq 10^9$

Ideias iniciais - Guloso

A primeira ideia que pode surgir é tentar pensar em uma estratégia gulosa para abordar os problemas, o que é totalmente válido como ideia, pois muitos problemas que parecem programação dinâmica podem ser resolvidos com ideias gulosas e vice-versa, vários problemas aparentemente gulosos podem ser resolvidos com algum tipo de programação dinâmica caso as ideias gulosas falhem. Vamos analisar algumas ideias gulosas para esse problema e constatar que não existem algum algoritmo guloso claro que funciona para uma versão geral desse problema.

Durante a análise dessas estratégia é comum construir-se casos para tentar quebrar o algoritmo guloso discutido, e não é recomendado provar tudo formalmente (em alguns casos mais complexos isso pode ser uma ferramente útil no entanto), pois criar casos muitas vezes é muito mais eficiente quando se discute o tempo utilizado, além de que, quando se cria um caso no qual o algoritmo não funciona, é possível se analisar com mais profundidade o problema e assim tentar corrigir a ideia inicial ou conseguir mais intuição para auxiliar no caminho à solução completa.

(Lembre-se que para cada ideia gulosa podem existir vários casos que a quebrem e só iremos apresentar um desses para cada ideia)

1. Escolher sempre o item mais leve, assim levando o máximo de itens possíveis. Essa ideia estaria certa caso os itens tivessem todos o mesmo valor, porém para o problema que temos essa estratégia é falha, pois ela simplesmente não leva em consideração o valor dos itens, logo poderíamos ter um caso com um item "pesado" porém muito valioso e vários itens "leves" com pouco valor, e a estratégia gulosa preferiría escolher os itens leves embora essa não seja a solução ótima.

2. Escolher sempre o item mais valioso. Assim como na estratégia anterior, estamos completamente ignorando uma das condições de cada item, nesse caso o peso, então poderíamos ter um caso em que o item mais valioso é muito pesado e ao mesmo tempo existir um conjunto com diversos elementos um pouco menos valiosos e mais leves, porém cuja soma de valores exceda àquela do item mais valioso, sendo assim uma escolha preferível.

3. Escolher sempre o item que tem o maior valor por unidade de peso ($\dfrac{v_i}{p_i}$). Nas ideias anteriores estávamos sempre ignorando algumas das propriedades dos itens, logo uma ideia para combiná-los seria escolher o elemento com maior valor por unidade de peso pois assim teríamos sempre o melhor retorno possível para cada espaço da mochila preenchido. Em muitos casos essa ideia está certa, caso pudéssemos por exemplo quebrar os itens em vários pedaços e levar partes fracionadas deles isso seria válido, porém nesse caso ainda temos uma restrição que não está sendo considerada e que é importante nesse problema: o espaço da mochila. Como os itens são inteiros e existe um limite de itens que podemos adicionar pode ser que, ao pegarmos um conjunto de itens com a maior "densidade", existam espaços vazios ou que serão preenchidos com itens de baixa "densidade", enquanto se pegarmos um conjunto de itens com "densidade" alta equilibrando o espaço utilizado teremos um conjunto com maior valor. Por exemplo, se tivermos os itens ($[peso, valor]$): $[8, 9], [5, 5], [5, 5]$ e uma mochila de capacidade 10, escolher os dois itens com peso e valor 5 resultará em um conjunto com valor maior que o conjunto formado só pelo elemento $[8, 9]$.

Nesse momento percebemos que pode ser difícil encontrar uma estratégia gulosa correta, pois o melhor elemento a se escolher em um determinado momento pode depender do espaço restante da mochila e dos elementos que ainda não foram escolhidos, portanto esse é um bom momento para tentar pensar em uma solução utilizando programação dinâmica.

Ideias iniciais - Força bruta

Podemos inicialmente utilizar a estratégia de força bruta para gerar todas as possibilidades de mochila, checar para cada uma delas se cabe na mochila e escolher a com maior valor dentre as válidas. O questionamento agora é como fazemos pra gerar todas as possibilidades. A primeira observação é que a ordem em que os itens são colocados não tem imporância para a mochila escolhida, pois, se uma sequência de elementos $S = (a_1, a_2, ..., a_n)$ é valida, todas as permutações dessa sequência também serão válidas, já que as únicas propriedades que importam são a soma dos pesos (para determinar se o conjunto é válido) e a soma dos valores (para determinar o valor do conjunto e assim poder comparar e escolher o maior dentre eles), e ambas são independentes da ordem em que os itens são escolhidos.

Com isso podemos perceber que dois conjuntos são diferente se e somente se os elementos que os compoem são diferentes, desse modo podemos utilizar uma função recursiva para gerar todos os casos da seguinte maneira: Consideramos adicionar os itens um por um em uma ordem específica (porém qualquer ordem serve), de modo que para cada possibilidade que consideramos podemos ou adicionar o item atual ou não adicioná-lo, gerando assim duas novas possibilidades. Repetimos esses passos até termos considerado adicionar todos os elementos. Segue uma implementação dessa busca exaustiva por todos os casos para melhor entendimento.

Otimizando a força bruta - Definindo os estados

Chegamos no momento discutido na última aula em que temos de encontrar um conjunto de estados que consiga agrupar várias possibilidades e assim comprimir o espaço de busca da função, que é exponencial no caso da força bruta.

A primeira coisa a se fazer é refletir e anotar as propriedades importantes para um conjunto que o permita agrupar com outros e ter o mesmo valor para a construção de novos estados. Nesse problema podemos perceber que se dois conjuntos tem o mesmo peso e o mesmo valor eles são "iguais" para a construção de próximos estados e para a resposta final mesmo que os itens individualmente que queremos escolher sejam diferentes.

Outro detalhe importante é que, diferentemente dos problemas apresentados na aula anterior -nos quais queríamos contar todos os conjuntos com algumas propriedades específicas-, esse problema nos pede para maximizar uma das propriedades considerando todos os conjuntos, e é aí que entra a importância da análise gulosa que fizemos inicialmente. Embora não seja possível comparar todos os conjuntos gulosamente podemos utilizar algumas das ideias apresentadas anteriormente para "remover" alguns estados inúteis caso estejamos comparando conjuntos com algumas propriedades fixas que escolhemos.

Nesse caso perceba que, se temos diversas possibilidades existentes com o mesmo peso, podemos aplicar o algoritmo guloso de escolher sempre a possibilidade com maior valor. De maneira semelhante se tivermos várias possibilidades com o mesmo valor, podemos aplicar o algoritmo guloso de sempre escolher a possibilidade com o menor peso e ele estará correto.

Com isso podemos "inverter" o estado da dp e levar um dos elementos que funcionaria como um estado para ser o valor que a função vai calcular. Nesse exemplo o que poderíamos fazer era, ao invés de ter uma dp: $f(peso, valor) =$ quantidade de conjuntos com esse peso e valor, poderíamos ter uma dp: $f(peso) =$ conjunto com esse peso que possui o maior valor, pois sabemos pelo argumento guloso que esse conjunto é sempre maior ou igual a todos os outros com esse mesmo peso. De maneira semelhante poderíamos ter também uma dp: $f(valor) =$ conjunto com esse valor que possui menor peso.

Para se escolher qual a melhor dessas que devemos escolher temos de olhar para os limites dados no problema e avaliar qual é o maior desses estados, para assim removermos e ter uma função mais eficiente. Nesse caso o maior peso de um estado válido é limitado pela capacidade da mochila, logo seu valor é $C \leq 10^5$, já o maior valor possível de uma mochila ocorre caso possamos colocar todos os itens juntos e eles todos tenham valor máximo, logo o limite é $N \cdot max(v_i) \leq 100 \cdot 10^9 = 10^{11}$. Com isso podemos perceber que é mais interessante nesse problema utilizar o peso como um estado e calcular o valor máximo como resultado da dp.

Otimização da força bruta - Montando a transição

Nesse momento temos uma função de dp que tem os estados otimizados porém precisamos conseguir gerar todas as possibilidades em cima desses estados para preencher a dp. Entretanto, do modo que eles estão definidos no momento, não é possível saber quais são os movimentos possíveis, visto que não salvamos nenhuma informação sobre quais itens já foram escolhidos, o que poderia acarretar na criação de uma transição que permita repetições de um mesmo elemento (algo que não queremos) e que simplesmente seja ineficiente demais, gerando assim respostas erradas em tempo sub-ótimo (uma ideia de transição incorreta que exemplifica os problemas apresentados aqui seria sempre, para um estado com peso fixo, tentar adicionar cada um dos itens disponíveis).

Para contornar esse problema precisamos trazer de volta uma ideia que utilizamos na implementação com força bruta, de modo que consigamos construir todos os subconjuntos sem a repetição de elementos. Para não repetirmos elementos precisamos de algum modo dizer quais elementos já foram adicionados (ou pelo menos já consideramos adicioná-los, então não precisamos fazer isso novamente), porém, como vimos que a ordem não importa, não precisamos salvar em um estado cada elemento que já consideramos individualmente, basta preencher o vetor em uma ordem fixa (lembrando que qualquer ordem serve), logo só precisamos salvar um estado $i$ indicando que todos os elementos com índice menor que $i$ já foram considerados e também sabemos que no momento iremos considerar exatamente o elemento $i$, levando em conta todas as possibilidades possíveis para ele (adicionar ou não adicionar), exatamente como fizemos na implementação com força bruta.

Com isso temos a seguinte definição da dp $dp(i, P) =$ conjunto com peso $p$, utilizando somente elementos com índice entre $1$ e $i$, cujo valor é máximo.
Eu recomendo sempre que for implementar uma dp escrever a definição explicitamente como feito acima. Caso queira também se pode escrever detalhadamente quais são as possibilidades da transição, as quais podem ser (existem várias maneiras de se implementar): "Ou eu não adiciono o item e continuo para o próximo estado com o mesmo peso, ou eu adiciono o item ao conjunto, adicionando o seu valor à resposta do conjunto somado ao melhor conjunto com o peso restante $P - p_i$. Ao final escolho o máximo entre essas duas possibilidades para ser o meu valor.", formalmente expressas como: $dp(i, P) = max(dp(i+1, P), dp(i+1, P - p_i) + v_i)$. Lembre-se também do caso base mas isso pode ser deixado como um detalhe para a implementação.

Agora que temos os estados e a transição prontos basta implementar, sempre se lembrando de verificar os casos base e implementar a memoização (calcular cada estado somente uma vez).

Segue o código para melhor entendimento (será apresentado tanto um código recursivo como iterativo).

Recursivo

Iterativo

Agora é a sua vez de implementar; para submeter utilize o seguinte link (está em inglês porém para submeter baste descer até o final da página, selecionar a linguagem (C++) na caixa indicada com Language, colar seu código na parte indicada com Source Code e clicar no botão Submit).

Existe outra versão muita parecida porém menos conhecida do problema no qual o peso dos itens e o tamanho da mochila podem ser muito grandes (até $10^9$), porém o valor máximo de cada item é pequeno (até $1000$). Com as ideias apresentadas nessa aula você pode tentar implementar essa versão e submeter nesse link. A ideia para conseguir construir a dp certa para esse problema é utilizar uma outra ideia gulosa que apresentamos na hora de montar os estados (salvar o valor em um estado e salvar a dp com o menor peso para esse valor).