O que é a Programação Dinâmica?
A programação dinâmica (em inglês, dynamic programming, ou apenas DP) é uma técnica de análise de problemas, de cariz recursivo, que divide a resolução de um problema em subproblemas mais simples, armazenando as sub-soluções já encontradas para acelerar as seguintes. É uma técnica que sacrifica memória para ter ganhos de desempenho.
O guardar de sub-soluções designa-se memoization. Costuma ser usado um vector ou matriz -- respectivamente para problemas com 1 ou 2 argumentos -- se as soluções podem ser indexadas. Noutros casos pode usar-se uma hash table.
Vejamos um exemplo básico com a sequência de Fibonacci.
A resolução directa é usando a própria definição recursiva:
public long fib(int n) {
if (n==0 || n== 1)
return 1;
return fib(n-2) + fib(n-1);
}
Esta versão tem complexidade exponencial.
Isto ocorre porque estamos a repetir a resolução de imensos sub-problemas. Por exemplo, fib(5) e fib(4) precisam ambos de calcular fib(3).
Mas isto é evitável se guardarmos essas sub-soluções. Se o fizermos conseguimos uma solução de complexidade linear.
O seguinte código usa um vector chamado sols para guardar sub-soluções. A escolha de um vector é apropriada dado que este problema apenas tem uma dimensão -- fib(n) -- e pode ser indexada pelo n:
private final int UNKNOWN = -1; // usamos um valor que não pode ser solução
public long fib(int n) {
long[] sols = new long[n+1];
sols[0] = sols[1] = 1; // no início, só se conhecem os casos base
for(int i=2; i<=n; i++)
sols[i] = UNKNOWN;
return fib(sols, n);
}
public long fib(long[] sols, int n) {
if (sols[n] == UNKNOWN)
sols[n] = fib(sols, n-2) + fib(sols, n-1);
return sols[n];
}
Até aqui, isto é apenas memorização, como referido nas aulas de AED.
O que realmente distingue a programação dinâmica é usar outras propriedades (que nem todos os problemas possuem, infelizmente): as sub-soluções que são respostas de sub-problemas têm de (a) fazer parte da solução do problema, e (b) os sub-problemas partilham sub-sub-problemas. Se isto se verificar, podemos ter ganhos muito grandes de desempenho.
Vejamos um exemplo clássico: o problema do Knapsack (apresentado na página 107 do livro do Halim).
Em português é conhecido pelo problema da mochila e citando a wikipedia:
O problema da mochila (em inglês, Knapsack problem) é um problema de optimização combinatória. O nome dá-se devido ao modelo de uma situação em que é necessário preencher uma mochila com [items] de diferentes pesos e valores. O objetivo é que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo.
Consideremos, por exemplo, os seguintes valores de input:
24 A capacidade da mochila é de 24 Kg
7 Existem 7 items
13 5 item 1 vale 13 unidades e pesa 5 Kg
30 10 item 2 vale 30 unidades e pesa 10 Kg
15 6 etc.
12 2
36 19
5 1
12 2
Por exemplo, se escolhermos o 1º e 5º item, obtemos um valor total de 49 unidades para 24 Kg. Mas é possível fazer melhor!
Vamos designar a capacidade por C. Entre os n items, o i-ésimo item por P_i, com valor V_i e peso W_i.
Seja o resultado dado por
total( conjunto dos items, capacidade ) = total( {P_1, P_2, ..., P_n}, C )
Uma resolução por DP precisa de uma definição recursiva deste total.
A base da recursão ocorre quando a capacidade é zero, ou quando não há items para escolher:
total( {}, C ) = 0
total( {...}, 0 ) = 0
Para lidar com o passo da recursão vamos considerar o primeiro item sendo o subproblema a chamada recursiva ao resto dos items. Deste modo, os subproblemas vão ficando mais simples, e chegaremos às bases da recursão.
O primeiro caso é quando temos um item tão pesado que não cabe na capacidade actual da mochila. Aqui, simplesmente não o escolhemos:
total( {P_i, ..., P_n}, C ) = total( {P_i+1, ..., P_n}, C ) , se W_i > C
Nos restantes casos teremos duas opções, ou escolhemos o item actual ou não:
O valor total que queremos será o maior dos resultados destas duas opções!
total( {P_i, ..., P_n}, C ) = max( V_i + total( {P_i+1, ..., P_n}, C - W_i ),
total( {P_i+1, ..., P_n}, C ) )
Vamos lá por isto em código. A versão de programação dinâmica escolhida é top-down (ie, começamos pelo problema original e vamos pedindo para calcular os problemas mais simples) e reflecte a estrutura recursiva da nossa solução:
static final int UNKNOWN = -1;
static int[] values, weigths;
static int[][] sols;
static int nProducts;
static int compute_sols(int i, int capacity) {
if (i==nProducts || capacity==0)
return 0;
if (sols[i][capacity] != UNKNOWN)
return sols[i][capacity];
if (weigths[i] > capacity)
return sols[i][capacity] = compute_sols(i+1, capacity);
return sols[i][capacity] =
Math.max( compute_sols(i+1, capacity),
values[i] + compute_sols(i+1, capacity - weigths[i]) );
}
Para ler um input como o indicado no início, e calcular o resultado:
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int capacity = sc.nextInt();
nProducts = sc.nextInt();
values = new int[nProducts];
weigths = new int[nProducts];
for (int i=0; i<nProducts; i++) {
values[i] = sc.nextInt();
weigths[i] = sc.nextInt();
}
sc.close();
sols = new int[nProducts][capacity+1];
for(int i=0; i<nProducts; i++)
for(int j=0; j<=capacity; j++)
sols[i][j] = UNKNOWN;
System.out.printf("%d\n", compute_sols(0, capacity));
}
A abordagem top-down evita calcular a tabela toda, apenas calcula os elementos estritamente necessários para calcular a solução. Se imprimirmos a tabela sols[][] com o input do exemplo obtemos o seguinte:
capacity: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
(val:13, wgt: 5) -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 75
(val:30, wgt:10) -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 62 -1 -1 -1 -1 74
(val:15, wgt: 6) -1 -1 -1 -1 -1 -1 -1 -1 -1 32 -1 -1 -1 -1 44 -1 -1 -1 -1 44 -1 -1 -1 -1 65
(val:12, wgt: 2) -1 -1 -1 17 -1 -1 -1 -1 29 29 -1 -1 -1 29 29 -1 -1 -1 29 36 -1 -1 -1 -1 65
(val:36, wgt:19) -1 5 -1 17 -1 -1 17 17 17 17 -1 17 17 17 17 -1 17 17 17 36 -1 -1 53 -1 53
(val: 5, wgt: 1) -1 5 -1 17 -1 17 17 17 17 17 -1 17 17 17 17 -1 17 17 17 17 -1 -1 17 -1 17
(val:12, wgt: 2) -1 0 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 -1 12 12 12 12
Os valores -1 são os valores por calcular. Podemos observar que cerca de metade da tabela não foi calculada.
Seria possível construir esta tabela, numa abordagem bottom-up, a partir da solução recursiva. Por exemplo, o elemento a azul foi calculado a partir dos elementos a verde. Confirme o porquê na definição recursiva que usa o máximo.
Se o quiséssemos fazer, dever-se-ia começar por preencher a primeira linha ou a última linha desta tabela?
Experimentem esta técnica do Knapsack resolvendo o UVa 10130.
Em resumo, a programação dinâmica aplica‑se a problemas com as seguintes características:
O primeiro ponto refere que deve ser possível definir recursivamente o problema.
O segundo ponto restringe‑se aos problemas onde a definição recursiva produz um algoritmo com complexidade muito elevada, como a exponencial.
O terceiro e último ponto descreve um ingrediente necessário para que a programação dinâmica funcione: a capacidade de construir um conjunto de soluções do mais simples para o mais complexo utilizando somente as sub-soluções óptimas. Caso contrário será necessário explorar todas as possibilidades não óptimas, o que resulta num algoritmo de complexidade excessiva.