Programação Dinâmica - Soma de Subconjunto (Subset Sum)

Soma de Subconjunto

Problema : Dado um conjunto de n números a[i] que a soma total é igual a M, e para algum K≤M, se existe um subconjunto dos números tais que a soma desse subconjunto dá exatamente K?

Solução 1:
Vamos usar uma tabela unidimensional m[0..M], m[b] indica se b pode ser alcançado.
for(i=0;i<=M;i++) m[i] = 0;
m[0]=1;
for(i=0;i
  for(j=M; j>= a[i]; j--)
    m[j] |= m[j-a[i]]

Observações: A idéia original é usar uma matriz bidimensional m[0..i-1][0..M], onde cada linha depende apenas da linha anterior. Mas utilizando um compressão de estados, podemos utilizar apenas um vetor unidimensional. Mas precisamos escrever o loop j na ordem reversa para evitar confusões.

Variações

Existem várias variações do problema da soma de subconjuntos

Doces para duas crianças: Os valores dos a[i]’s representam os valores dos doces. Nós queremos dividir igualmente os doces entre as duas crianças ou da maneira mais justa. Agora o problema não é encontrar um subconjunto com soma fixa K. Nós queremos encontrar um certo K mais próximo de M/2.
http://br.spoj.pl/problems/TESOURO/
http://www.spoj.pl/problems/FCANDY/


Soma de subconjunto com múltiplos suprimentos: Cada elemento a[i] pode ser usado quantas vezes você precise na soma para alcançar o valor K? Talvez você demore ou não para ver a solução. A solução é apenas inverter a direção do loop j na solução j.

Troco (coin change): Agora cada a[i] representam moedas, você quer passar um troco de exatamente K. Talvez existam várias maneiras de você fazer isso, então você quer minimizar (ou maximiza) o número de moedas que você precisa usar. A estrutura da solução não precisa ser alterada, nós precisamos apenas mudar o significado do vetor m. Agora m[b] não será 0 ou 1, será exatamente o número mínimo de moedas que você precisa para alcançar b.
https://br.spoj.pl/problems/MOEDAS/
http://www.spoj.pl/problems/NOCHANGE/


Doces para três crianças: Nós queremos agora dividir os doces mais equilibradamente o possível entre as três crianças. A questão é o que representa “mais equilibradamente o possível”. A solução pode ser feita de diferentes maneiras, mas a estrutura da solução são quase as mesmas. Use um vetor bidimensional m [][], m[b][c] indica se podemos ou não dividir os doces de maneira que b doces vão para a primeira criança, c doces para a segunda criança e o restante vai para a terceira criança.

Contando o troco (couting change): Os a[i]s continuam representando moedas, agora você quer saber quantas maneiras você pode passar o troco K. O número de maneiras de trocar uma quantidade A usando N tipos de moedas é igual a:
1. O número de maneiras de trocar a quantidade A usando todas as moedas anteriores, +
2. O número de maneiras de trocar a quantidade A-D usando todos os N tipos de moedas, onde D é o valor da n enésima moeda.

A árvore de recursão do processo vai reduzir gradualmente o valor de A, então podemos usar estas regras, para determinar o número de maneiras de trocar um certo valor
1. Se A == 0, então vamos contar 1 maneiras.
2. Se A <=0, então vamos contar 0 maneiras
3. Se N tipos de moedas == 0, então vamos contar 0 maneiras.

int coin[] = {1,5,10,25,50};
int count[MAX_MONEY+1];
memset(count,0,sizeof(count));
count[0] = 1;
for (int i=0;i
for (int j=coin[i];j<=MAX_MONEY;++j)
count[j] += count[j-coin[i]];

Problema
http://br.spoj.pl/problems/SEQUENCI/