O Problema da Mochila
O problema mais clássico de Progração Dinâmica talvez seja o Knapsack, ou o problema da mochila. De maneira geral, um ladrão irá roubar uma casa com uma mochila que suporta um peso \(s\). Ele vê \(n\) objetos na casa e sabe estimar o peso \(p_i\) e o valor \(v_i\) de cada objeto \(i\). Com essas informações, qual o maior valor que o ladrão pode roubar sem rasgar sua mochila? Assim como nesse exemplo, Programação Dinâmica é muito comum em problemas que parecem ser resolvidos por algoritmos gulosos, mas não podem. No caso, o primeiro pensamento de alguém pode ser sempre pegar o objeto de maior valor que ainda não foi colocado na mochila, até que não caiba mais nenhum, mas essa ideia é facilmente quebrada com o seguinte exemplo: uma mochila que suporta peso 12 e três objetos cujos pesos são 10, 6 e 6 e seus respectivos valores são 9, 5 e 5.
O programa guloso iria preferir o objeto mais valioso (de valor 9 e peso 10) e não caberá nenhum dos outros dois. Porém, é melhor que coloquemos na mochila os outros dois, que somados têm peso 12 (cabe na mochila) e valor 10 (maior que 9). Depois de pensar um pouco mais, você pode pensar na “densidade de valor” do objeto. Faria um guloso que pusesse na mochila os objetos de maior “valor por grama”. Porém, o mesmo caso mostrado acima mostra que esse guloso tomaria a mesma decisão errada que o outro. O que fazer então? Uma DP! Vale ressaltar que, na maioria das vezes (inclusive agora), faremos uma DP Top-Down por ser mais fácil e didática que a Bottom-Up.
Vamos criar dois vetores apenas para guardarmos o peso e o valor de cada objeto, assim, o peso do objeto i estará salvo em peso[i], e o seu valor estará em valor[i]. Para responder o problema, tente pensar em um estado da DP como: estando os objetos em fila (indexados de \(0\) a \(n-1\)), qual o máximo que o ladrão pode roubar se ainda tiver disponível todos os objetos a partir de uma certa posição obj da fila, e a mochila ainda aguentar o peso aguenta sem rasgar, ou seja, tente implementar a função int knapsack(int obj, int aguenta){}. Ela deverá receber o número do objeto que está sendo verificado e quanto peso a mochila ainda aguenta, retornando, para tais parâmetros, o maior valor que que o ladrão pode roubar se ainda sobrar aguenta gramas na mochila e você puder colocar ou não colocar todos os objetos a partir de obj. A ideia é, dados os objetos em fila, em ordem qualquer de entrada, testá-los, um a um, se é melhor colocá-lo, ou não, testando todas as possibilidades com um DP. Para isso basta analisarmos o estado em que a DP ficaria se colocássemos e se não colocássemos o objeto que estamos olhando, e escolher o melhor deles.
Em uma DP, antes de qualquer coisa, veremos se o estado que estamos olhando já foi calculado, ou seja, se em algum momento já chamamos a função para os parâmetros atuais (“dp(obj, aguenta)”). Se isso ocorrer, deverá estar salvo na nossa tabela de DP, de nome tab, nos índices obj e aguenta. Vamos inicializá-la com todos os valores iguais a -1 com o memset e quando calcularmos algum valor, vamos substitui-lo na tabela, ou seja, se o valor salvo nela, para os parâmetros que estamos olhando, for maior ou igual a zero (“if(tab[obj][aguenta]>=0)”) retornamos o valor que está salvo lá (“return tab[obj][aguenta];”).
As bases da DP são duas: se já olharmos todos os objetos da fila, ou seja, já passamos todas as posições e chegamos em n (“if(obj==n)”), ou se ela não aguentar mais peso algum (“if(aguenta==0)”), não podemos mais adicionar nada na mochila, ou seja, a função deve retornar valor 0.
Nos demais casos da DP, temos que olhar se o melhor é colocar ou não o objeto, então vejamos o que ocorrer nos dois casos! Vamos declarar o int nao_coloca, que receberá o maior valor que podemos obter sem colocar obj na mochila, e testando todos os outros da fila. Assim, o estado em que ficaremos seria: vamos olhar o próximo objeto (obj+1) e a mochila continuará ainda aguentando o mesmo que antes, pois não colocamos obj na mochila, logo, executamos o comando “nao_coloca=knapsack(obj+1, aguenta);”. Agora, vamos testar se é possível colocar obj, ou seja, se o peso de obj não é maior que o peso que a mochila aguenta (“f(peso[obj]<=aguenta)”). Se for possível, devemos retornar que o máximo que podemos obter equivale ao valor do objeto que colocamos somado do melhor que podemos testando o próximo objeto, sendo que agora a mochila aguentará o que ela aguentava antes, subtraído do peso de obj. Em outras palavras, criaríamos a variável int coloca e atribuiríamos a ela o valor valor[obj]+knapsack(obj+1, aguenta-peso[obj). Feito isso, retornamos o melhor, ou seja, o maior valor dentre o de colocar ou não colocar obj na mochila. Para isso, usaremos a função max da biblioteca de C++ algorithm, que recebe dois objetos quaisquer como parâmetros e retorna o maior deles, segundo os operadores “<” e “>”. Retornaremos, portanto o maior dentre coloca e nao_coloca, lembrando de salvar antes o valor na tabela de DP (“return tab[obj][aguenta]=max(coloca, nao_coloca;”).
Caso a função continue sua execução sem retornar, então não foi possível colocar o objeto e só temos uma opção: não colocá-lo, logo a função deve retornar o valor de nao_coloca, também salvando-o antes na tabela de DP. Assim, basta lemos todos os pesos e valores dos objetos na entrada e depois retornarmos o melhor possível dentre colocar ou não o primeiro objeto da fila, sendo que a mochila ainda aguenta seu valor inicial \(s\), ou seja, devemos imprimir o valor de knapsack(0, s). Segue o código comentado para melhor entendimento:
#include <algorithm>
using namespace std;
// defino os maiores valores de n e s como 1010
#define MAXN 1010
#define MAXS 1010
// declaro as variáveis que a função utiliza
int n, valor[MAXN], peso[MAXN], tab[MAXN][MAXS]
int knapsack(int obj, int aguenta){
// se já calculamos esse estado da dp, retornamos o resultado salvo
if(tab[obj][aguenta]>=0) return tab[obj][aguenta];
// se não houver mais objetos ou espaço na mochila, retorno 0, pois não posso mais botar nada
if(obj==n or !aguenta) return tab[obj][aguenta]=0;
// não colocar avança para o estado em que tentmos o próximo, com o mesmo espaço disponível
int nao_coloca=knapsack(obj+1, aguenta);
// se for possível colocar o objeto
if(peso[obj]<=aguenta){
// o melhor atingível é o valor dele mais o melhor entre colocar ou não os próximos
// que é o resultado do estado da dp em que olhamos o próximo objeto
// mas agora a mpchila aguenta o que aguentava antes menos o peso que coloquei nela
int coloca=valor[obj]+knapsack(obj+1, aguenta-peso[obj]);
// e a função deve retornar o melhor entre colocar ou não colocar
return tab[obj][aguenta]=max(coloca, nao_coloca);
}
// se a função não retornou ainda, então ela não entrou no if
// logo não era possível colocar o objeto
return tab[obj][aguenta]=nao_coloca; // então retorno o valor de não colocá-lo
}Lembre-se de, antes de chamar a função na main, fazer com que todos os valores de tab se tornem -1, com o comando memset(tab,-1,sizeof tab), indicando que nenhum estado foi calculado ainda.
Note alguns pontos fundamentais da DP: por que ela funciona? Para uma DP funcionar, precisamos das mesmas condições de uma recursão.
- Os casos de base são resolvidos de maneira direta, nunca chamando uma recursão
- Qualquer estado da DP que não seja um caso base chama uma recursão que, no fim, resultará em um caso base. No Knapsack, note que a recursão sempre chama uma função para um objeto de índice maior, logo, ela eventualmente alcançará o índice \(n\), que é um caso base e será resolvido sem chamada recursiva.
Note que cada passo da DP tem complexidade constante, e há, no máximo,\(n\times s\) estados, logo a complexidade do algoritm é \(O(n\cdot s)\). Essa ideia do Knapsack de observar se vamos colocar ou não cada uma das opções disponíveis e usar uma DP para testar todas é amplamente conhecida nos meios de programação competitiva, e vários problemas são construídos em cima disso