ProgramaçãoDinâmica

Programação dinâmica consiste em dividir um problema em subproblemas e usar a solução dos subproblemas para resolver o problema original.

Por que esse nome?

Da auto-biografia de Richard Ernest Bellman (Eye of the Hurricane: An Autobiography (1984)):

I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, Where did the name, dynamic programming, come from? The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, “programming” I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying I thought, lets kill two birds with one stone. Lets take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is its impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. Its impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.

Para entender melhor programação dinâmica vamos primeiro estudar o conceito de indução matemática.

Princípio da Indução

Uma propriedade $P$ é válida $\forall n \ge n_0$ se for possível provar que:

  1. $P(n_0)$ é válida
  2. Se $P(k)$ então $P(k+1)$, $\forall k \in Z$ tal que $k \ge n_0$

Chamamos de caso base a primeira proposição.
Chamamos de passo indutivo a segunda proposição.

Exemplo: Seja uma fila de dominós.

  1. O primeiro dominó cai
  2. Se algum dominó cai então o próximo dominó também cai

Se os dois itens acima são verdadeiros, logo todos os dominós caem

Problemas Clássicos

Coin Change

Definição

Seja o conjunto de moedas $C = \{c_1, c_2, \dots , c_n\}$.
Desejamos dar um troco $V$ usando o mínimo de moedas possível.

Solução

Seja $S(v) =$ menor número de moedas que precisamos para dar o troco $v$.
Caso base: $S(c_i) = 1, \forall c_i \in C$
Passo Indutivo: $S(v) = min\{S(v - c_i), \forall c_i \in C\}$

A ideia da solução é para um valor $v$ tentamos utilizar a moeda $c_i$ e resolvemos o problema para um outro valor $v - c_i$.
Vamos selecionar a moeda que possui o menor valor $S(v - c_i)$.

Código
#include <stdio.h>
#include <algorithm>
#define MAX_VALUE 100010
#define MAX_COINS 1010
using namespace std;
 
int S[MAX_VALUE], c[MAX_COINS];
int best[MAX_VALUE]; // Moeda utilizada em cada valor
int K;
int prof; // Variável de profundidade da recursão. Auxilia na impressão da pilha de função.
 
void go(int v) {
    for (int i = 0; i < prof; i++) {
        printf(" ");
    }
    printf("%d\n", v);
    prof++;
    if (S[v] != -1) {
        prof--;
        return;
    }
 
    S[v] = 10000000;
    // Para cada moeda
    for (int i = 0; i < K; i++) {
        // Se pode usar a moeda com o valor 'v' atual
        if (v - c[i] > 0) {
            go(v - c[i]);
            if (S[v - c[i]] + 1 < S[v]) {
                S[v] = S[v - c[i]] + 1;
                best[v] = i;
            }
        }
    }
    prof--;
}
 
// Imprime as moedas utilizadas
void Imprime(int v) {
    printf("%d ", c[best[v]]);
    if (v - c[best[v]] > 0) {
        Imprime(v - c[best[v]]);
    }
}
 
int main() {
    int V;
    scanf(" %d %d", &K, &V);
    while (K != 0) {
        for (int i = 0; i < K; i++) {
            scanf(" %d", &c[i]);
        }
 
        for(int i = 0; i <= V; i++) {
            S[i] = -1;
        }
        for (int i = 0; i < K; i++) {
            S[c[i]] = 1;
            best[c[i]] = i;
        }
        prof = 0;
        go(V);
        printf("%d\n", S[V]);
 
        Imprime(V);
        printf("\n");
 
        scanf(" %d %d", &K, &V);
    }
}

Max SubArray

Definição

Seja o array $V = [v_1, v_2, \dots , v_n]$.
Desejamos encontrar o subarray contínuo $[v_i, v_{i+1}, \dots , v_{j-1}, v_j]$ de soma máxima e tamanho pelo menos 1.
Exemplo: Seja $V = [2, -3, 5, 4, -1, 2, -8, 3]$. O subarray de soma máxima é $[5, 4, -1, 2]$.

Solução

Seja $S(i) =$ valor do maior subarray que termina em $i$.
Caso base: $S(0) = v[0]$
Passo Indutivo: $S(i) = max\{S(i-1) + v[i], v[i]\}$

O maior subarray que termina em $i$ é o subarray que termina em $i-1$ somado de $v[i]$ ou o próprio $v[i]$ sozinho.
A resposta para o problema é o maior valor de $S(i)$.

Código
#include <stdio.h>
#include <algorithm>
#define TAM 10010
 
using namespace std;
 
int N;
int v[TAM];
int S_td[TAM], S_bu[TAM];
 
void topDown(int i) {
    if (i == 0) {
        S_td[0] = v[0];
        return;
    }
    topDown(i-1);
    S_td[i] = max(S_td[i-1] + v[i], v[i]);
}
 
void BottomUp() {
    S_bu[0] = v[0];
    for (int i = 1; i < N; i++) {
        S_bu[i] = max(S_bu[i-1] + v[i], v[i]);
    }
}
 
int main() {
    scanf(" %d ", &N);
    while (N != 0) {
        for (int i = 0; i < N; i++) {
            scanf(" %d ", &v[i]);
        }
 
        topDown(N-1);
        int ansTD = S_td[0];
        for (int i = 1; i < N; i++) {
            ansTD = max(ansTD, S_td[i]);
        }
 
        BottomUp();
        int ansBU = S_bu[0];
        for (int i = 1; i < N; i++) {
            ansBU = max(ansBU, S_bu[i]);
        }
 
        printf("TopDown: %d\n", ansTD);
        printf("BottomUp: %d\n", ansBU);
 
        scanf(" %d ", &N);
    }
 
    return 0;
}

Mochila

Definição

Um ladrão entra em uma casa que possui $n$ itens, o item $i$ possui peso $P[i]$ e valor $V[i]$.
O ladrão tem uma mochila que suporta um peso de até $X$. Ele deseja carregar itens cuja soma dos valores seja a maior possível.

Solução

Seja $S(i, j) =$ maior valor utilizando um subconjunto dos itens $\{1, \dots , i\}$, cuja soma dos pesos seja $j$.
Caso base: $S(0, P[0]) = V[0]$
Passo Indutivo: $S(i, j) = max\{S(i-1, j), S(i-1, j - P[i]) + V[i]\}$

Para S(i, j) temos duas opções: não utilizar o item $i$ e portanto pegar melhor solução usando os itens de $0$ até $i-1$, ou utilizar o item $i$ com a solução de $S(i-1, j - P[i])$.
A resposta é o máximo de $S(n, j), \forall j$.

Mais referências

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License