Marathoncode: Programação Dinâmica - Soma de Subconjunto (Subset Sum)
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?
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;
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.
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