1389. Pedido de Desculpas

Olá meus amigos nerds, hoje falaremos um pouco de um dos problemas mais clássicos de programação dinâmica, o problema da mochila. E isso, graças ao nosso amigo Cuca, que saiu para jogar futebol e se esqueceu de se encontrar com sua namorada. 

Mais especificamente, o problema 1389. Pedido de Desculpas nos pede que ajudemos Cuca a escrever um pedido de desculpas com o maior número de repetições da palavra desculpa. Para isso Cuca nos forneceu um conjunto pré escolhido de frases e quer usar essas frases para preencher um cartão de desculpas que cabe apenas um número limitado de caracteres.

Solução

O problema aqui é bastante simples, apenas se você já estudou um pouco de algoritmos (e consequentemente, conhece o problema da mochila booleana). Observe que podemos mapeá-lo da seguinte forma:

cartão = mochila
tamanho das frases = peso dos objetos
# de desculpas por frase = valor ($) dos objetos

Mochila Booleana

O problema da mochila é 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 objetos 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.

O problema da mochila é um dos 21 problemas NP-completos de Richard Karp. Isso quer dizer que sua solução tem complexidade O(2^n). Observe que, esse problema pode ser resolvido como um problema de decisão, ou seja, para cada objeto, decida se ele deve ou não ser colocado na mochila. Uma forma simples de se decidir pela adição ou não de um objeto é gerando todos os subconjuntos de objetos e escolhendo o subconjunto de maior valor:

melhorSolucao=0
foreach subconjunto dos objetos
    valor = calcule o valor desse subconjunto
    if valor > melhorSolucao
         melhorSolucao = valor

Felizmente, existe uma solução pseudo polinomial para o problema. Suponha que temos n objetos, sendo que o i-ésimo objeto tem valor v[i] e peso p[i]. Podemos usar uma estrutura recursiva para resolver o problema da mochila booleana por programação dinâmica. A ideia é guardar em uma tabela (mochila) as soluções das (sub)instâncias do problema. A tabela é definida como:

mochila[# de objetos][capacidadeMáximaMochila] =  maior valor alcançado com uma mochila de capacidade capacidadeMáximaMochila  e itens 1,...,# de objetos

Lembrando que ou um item é necessário para alcançar o valor ótimo, ou não é, então podemos expressar o valor dos elementos de nossa tabela como:

mochila[i][peso] = max(
               mochila[i-1][peso], //o elemento i não é usado pela solução ótima
               v[i] + mochila[i-1][peso-p[i]] //o elemento i é usado pela solução ótima
              )

como condição de contorno caso p[i] > peso => mochila[i][peso] = mochila[i-1][peso]

Observe que essa solução tem complexidade O(# de objetos * capacidadeMáximaMochila). Mas, anteriormente eu não afirmei que o problema da mochila é NP-completo? Se você ficou curioso a esse respeito aqui e aqui você poderá encontrar a justificativa.

Dei aqui apenas uma explicação superficial sobre o problema da mochila, se você não o conhecia e achou interessante uma ótima referência para uma leitura mais aprofundada é o livro do Cormen (Introduction to Algorithms).

Implementação