Soma de Sub-Conjuntos

Existe uma imensa (infinita?) quantidade de algorítimos dos quais eu tenho apenas uma vaga noção (e um número imensamente maior de algorítimos dos quais eu nem tenho uma vaga noção). Um mês após uma tentativa mal sucedida de resolver um problema do SPOJ Brasil, eu percebi que ele tinha certa semelhança com um problema que eu tinha visto uma década atrás e do qual eu lembrava apenas o nome (knapsack).

Compartilho abaixo o que eu aprendi sobre o problema da "soma de sub-conjuntos".

O Problema do SPOJ Brasil

O problema "Caça ao Tesouro" foi apresentado na Olimpíada Brasileira de Informática de 2002. O texto completo está no site do SPOJ Brasil, mas segue aqui um resumo.

João e José saíram a caça de um tesouro. Durante a procura, os dois acumularam um certo valor (que pode ser diferente entre os dois). O tesouro é composto de várias joias, com valores diferentes. O problema é saber se é possível repartir estas joias entre os dois, de tal forma que os dois fiquem com o mesmo valor, considerando o que já acumularam antes.

Pegando o primeiro exemplo do enunciado: João acumulou 10, José acumulou 20 e existem 4 joias a repartir, com valores 3, 8, 7 e 2. Para ficarem com valores iguais, José precisa receber joias no valor de 15 e João joias no valor de 5. Esta divisão é possível: José pega as joias de valor 8 e 7 e João as joias de valor 3 e 2.

Um pouco de rabisco e percebe-se que a quantidade de combinações sobe exponencialmente: para n joias temos 2^n conjuntos possíveis (se isto não estiver claro, pense em binário: cada joia pode estar ou não no conjunto portanto cada combinação pode ser vista como um número binário com n dígitos onde o dígito i indica se a joia i está presente (1) ou ausente (0) no conjunto).

O problema estipula que devem ser tratados casos com até 100 joias em um tempo inferior a um segundo. Antes de ir em frente, pense um pouco como você faria isto!

O Problema Knapsack ("Mochila")

Da-se o nome de knapsack a uma classe de problemas onde você quer selecionar um subconjunto de elementos de forma a maximizar a soma de uma característica destes elementos ou mesmo tempo em que respeita um limite máximo para a soma de outra característica deles (ou mesmo vários limites considerando várias características simultaneamente).

Uma forma simples de entender isto é pensar em uma mochila que aguenta um certo peso máximo. Queremos colocar nela vários itens, cada um com um peso e um valor, de forma a respeitar o peso máximo e a obter o maior valor total possível.

Este é um problema NP-complete: embora seja rápido verificar se uma solução é válida, não é conhecido nenhum algorítimo eficiente para resolvê-lo de forma genérica.

O problema da "Caça ao Tesouro" corresponde a um caso específico do knapsack: a soma de sub-conjuntos (subset sum).

O Problema da Soma de Sub-Conjuntos

Neste problema, queremos descobrir se existe um sub-conjunto de um conjunto de valores cuja soma seja um certo valor. No caso da "Caça ao Tesouro", o conjunto de valores são os valores das joias e a soma desejada é a que deixa João e José com o mesmo valor total.

O problema da soma de sub-conjuntos também é NP-complete, porém existem algumas soluções viáveis para valores limitados (para valores não limitados, pode-se apelar para soluções aproximadas).

A solução que eu implementei vem de uma referência externa (PDF) do artigo a respeito na Wikipedia. Embora sejam notas de aula da universidade de Berkeley, parece que tem um pequeno engano ou omissão.

De qualquer forma, o método é muito engenhoso. Para ser viável, não somente n (número de elementos no conjunto) deve ser pequeno, mas também o valor da soma desejada (o que não é intuitivo).

O método monta uma matriz lógica bi-dimensional onde o elemento [i, j] indica se é possível montar um sub-conjunto cuja soma seja j usando os primeiros i elementos do conjunto. Vamos chamar esta tabela de m, o valor do item i do conjunto de v[i] e a soma desejada de s. A resposta que desejamos estará em m[n][s].

Veja como fica a tabela para o exemplo lá de cima, com o conjunto { 3, 8, 7, 2}:

1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
-  -  x  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
-  -  x  -  -  -  -  x  -  -  x  -  -  -  -  -  -  -  -  -
-  -  x  -  -  -  x  x  -  x  x  -  -  -  x  -  -  x  -  -
-  x  x  -  x  -  x  x  x  x  x  x  x  -  x  -  x  x  -  x

O segredo é que esta matriz pode ser montada interativamente.

Vamos considerar a primeira linha desta tabela, que indica as somas possíveis para sub-conjuntos que contenham somente o primeiro elemento. Obviamente a única soma possível é o valor do primeiro elemento. Na linguagem dos matemáticos, m[1][v[1]] é verdadeiro e m[1][j] é zero para todo j diferente de v[i].

Vejamos agora uma linha genérica i, com i > 1. Neste ponto a linha i-1 indica as somas possíveis de serem gerados com os primeiros i-1 elementos, na linha i precisamos acrescentar as somas que poderão ser geradas com a adição de v[i]. A linha i terá, portanto, todos os valores verdadeiros da linha i-1, mais v[i] e mais os valores s tais que m[i-1][s - v[i]] seja verdadeiro (em outras palavras, se conseguimos fazer s-v[i] com os primeiros i-1 elementos, somando o v[i] conseguiremos obter s). Obs.: no documento acima falta considerar v[i].

Qual o tamanho desta tabela? Da forma como desenhada acima, ela terá n linhas. Como nosso interesse é chegar ao valor s, podemos nos limitar a s colunas. O grosso do nosso algorítimo será um laço variando j de 1 a s (varrendo as colunas), dentro de um laço de 2 a n (varrendo as linhas). Desta forma, podemos dizer grosseiramente que o tempo dependerá do produto n x s. Em termos de armazenamento, não precisamos guardar as n linhas, basta guardar a atual e a anterior.

Dividindo o Tesouro

Com a teoria acima, fica quase fácil resolver o problema do SPOJ (e só tomar cuidado com alguns casos especiais e não esquecer de comentar o código de debug, coisas que eu não fiz no início).

Pela descrição, estamos limitados a até 100 valores, cada um deles limitado até 100, o que dá uma soma máxima de 10000. Ficamos então com uma tabela completa de um milhão de elementos. Cada elemento poderia ser um simples bit, mas eu gastei um byte; além disso coloquei as 100 linhas ao invés de apenas duas. Devido a meu passado, com barreiras de 64K, e o meu presente, programando microcontroladores, não é de estranhar que o meu cabelo tenha arrepiado quando declarei a matriz m com 100 linhas e 10000 colunas. Bah, hoje em dia 1MByte é nada em um PC.

O código final ficou assim:

#include <stdio.h>

int v[101];
char m[101][10001];

int main (void)
{
  int x, y, n;
  int i, j, max, b;
  int iCaso = 1;
  int result;

  for (;;)
  {
      scanf ("%d %d %d\n", &x, &y, &n);
      if ((x == 0) && (y == 0) && (n == 0))
          break;
      max = 0;
      for (i = 1; i <= n; i++)
      {
          scanf ("%d\n", &v[i]);
          max += v[i];
      }
      if (x > y)
          b = max + y - x;
      else
          b = max + x - y;
      if ((b < 0) || ((b & 1) != 0))
          result = 0;
      else if (b == 0)
          result = 1;
      else
      {
          b = b/2;
          //printf ("Alvo=%d\n", b);
          for (i = 1; i <= b; i++)
              m[1][i] = 0;
          m[1][v[1]] = 1;
          for (i = 2; i <= n; i++)
          {
              for (j = 1; j <= b; j++)
              {
                  if (j == v[i])
                      m[i][j] = 1;
                  else if (j < v[i])
                      m[i][j] = m[i-1][j];
                  else if (m[i-1][j] || m[i-1][j - v[i]])
                      m[i][j] = 1;
                  else
                      m[i][j] = 0;
              }
          }
          result = m[n][b];
          //for (i = 1; i <= n; i++)
          //{
          //    for (j = 1; j <= b; j++)
          //        printf ("%c ", m[i][j] ? '*' : '.');
          //    printf ("\n");
          //}
      }
      printf ("Teste %d\n%c\n\n", iCaso, result ? 'S' : 'N');
      iCaso++;
  }

  return 0;
}