Suponha que p1, p2, … , pn são os valores dos cheques que você emitiu durante o mês. No fim do mês, o banco debita uma quantia c em sua conta. Quais dos cheques foram debitados?
Este é um exemplo do problema subset sum,
também conhecido como exact subset sum.
Poderíamos chamar o problema de soma de subconjunto
,
mas é melhor usar o nome tradicional em inglês.
Esse problema é um caso especial do problema da mochila booleana.
Esta página usa a estrutura recursiva do problema
para desenvolver dois algoritmo de força bruta
:
um algoritmo exponencial de enumeração
e um algoritmo de programação dinâmica.
Dado um vetor númerico p[1 .. n] e um subconjunto X de {1, 2, … , n}, denotaremos por p(X) a soma ∑i∈X p[i] . Essa notação é útil para formalizar o seguinte problema.
Problema subset sum: Dado um vetor p[1 .. n] de números naturais e um número natural c, decidir se existe um subconjunto X de {1, 2, … , n} tal que p(X) = c.
Os elementos de p[1 .. n] são chamados pesos e o parâmetro c é chamado alvo. O problema consiste em decidir se algum subconjunto de 1 .. n tem soma dos pesos igual ao alvo.
Toda instância do problema tem solução.
Uma solução sim
pode ser representada por 1
e uma solução não
por 0.
Uma instância com n = 0
tem solução sim
se e somente se o alvo é 0.
Embora o problema peça apenas sim
ou não
como resposta,
qualquer algoritmo para o problema pode ser modificado para produzir,
junto com um sim
,
um conjunto X tal que
p(X) = c.
(Veja um dos exercícios abaixo.)
Exemplo A:
A instância do problema que tem pesos
p = (30, 40, 10, 15, 10, 60, 54) e
alvo c = 55
tem solução sim
.
O conjunto { 2, 4 }
tem soma de pesos igual ao alvo.
O conjunto { 1, 4, 5 }
também tem essa propriedade.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| p | 30 | 40 | 10 | 15 | 10 | 60 | 54 |
| ☑ | ☑ | ||||||
| ☑ | ☑ | ☑ |
não.
O problema subset sum tem uma estrutura recursiva óbvia.
De fato, é fácil verificar a seguinte observação:
uma instância ( p, n, c)
do problema tem solução 1 (ou seja, sim
)
se e somente se
pelo menos uma das subinstâncias
( p, n − 1, c ) e ( p, n − 1, c − p[n] )
tem solução 1. Essa estrutura recursiva óbvia leva imediatamente ao seguinte algoritmo:
| Subset-Sum-R (p, n, c) |
| 1 . se n = 0 |
| 2 .ooo se c = 0 |
3
.oooooo
devolva 1 e pare
▷ sim |
4
.ooo
devolva 0 e pare
▷ não |
| 5 . b := Subset-Sum-R (p, n − 1, c) |
| 6 . se b = 0 e p[n] ≤ c |
| 7 .ooo b := Subset-Sum-R (p, n − 1, c − p[n]) |
| 8 . devolva b |
Exemplo B: Aplique o algoritmo Subset-Sum-R à instância que tem pesos (10, 15, 30) e alvo 40. A execução do algoritmo pode ser representada por uma árvore binária cujos nós são subinstâncias da instância original. O conjunto de índices da subinstância está indicado na parte superior do nó e o alvo na parte inferior.
| 1..3 | ||
| / \ | ||
| 1..2 | 1..2 |
A figura mostra os dois primeiros níveis da execução do algoritmo. Complete a figura desenhando os demais níveis.
Quanto tempo o algoritmo consome? Denote por T(n) o consumo de tempo no pior caso. Se cada execução de cada linha do código — exceto as linhas 5 e 7 — consome 1 unidade de tempo, T(n) satisfaz a recorrência
T(n) = 3 + T(n−1) + T(n−1)
quando n ≥ 1 e tem valor inicial T(0) = 3. A solução dessa recorrência está em Θ(2n). Assim, o consumo de tempo do algoritmo está em Θ(2n) no pior caso.
O algoritmo Subset-Sum-R é exponencial pois examina todos os 2n subconjuntos de { 1, … , n } no pior caso. Pode-se dizer que o algoritmo usa força bruta para resolver o problema.
Note porém que a quantidade de espaço de trabalho
usada por
Subset-Sum-R
é apenas Ο(n),
pois a altura da pilha de recursão nunca passa dos n elementos.
não. Mostre que, para cada subconjunto X de 1 .. n, o algoritmo é invocado com segundo argumento 0 e terceiro argumento c − p(X). Por exemplo, quando n = 4 e X = {2, 4}, alguma invocação do algoritmo terá argumentos (p, 0, (c−p[4])−p[2]).)
Seja m = ⌊n/2⌋, A = { 1, … , m } e B = { m+1, … , n }. Sejam A[1], A[2], … , A[2m] todos os subconjuntos de A. Para k = 1, … , 2m, seja s[k] = c − p(A[k]). Rearranje o vetor s[1 .. 2m] em ordem crescente. Para cada subconjunto C de B, use busca binária para decidir se a soma p(C) está em s[1 .. 2m]. Em caso afirmativo, devolva 1. Se nenhuma das somas da forma p(C) estiver em s[1 .. 2m], devolva 0.
Descreva o algoritmo em código. Analise o consumo de tempo do algoritmo. Analise o consumo de espaço.
O algoritmo Subset-Sum-R é lento porque examina todos os subconjuntos do intervalo 1 .. n. Para tentar construir um algoritmo mais rápido, vamos recorrer à técnica da programação dinâmica e guardar em uma tabela as soluções das subinstâncias da instância original. Com isso, a solução da instância original poderá ser calculada a partir das soluções armazenadas na tabela.
| Subset-Sum-Prog-Din (p, n, c) |
| 11 . para i crescendo de 0 até n |
| 12 .ooo t[i, 0] := 1 |
| 13 . para j crescendo de 1 até c |
| 14 .ooo t[0, j] := 0 |
| 15 .ooo para i crescendo de 1 até n |
| 16 .oooooo b := t[i − 1, j] |
| 17 .oooooo se b = 0 e p[i] ≤ j |
| 18 .ooooooooo b := t[i − 1, j − p[i]] |
| 19 .oooooo t[i, j] := b |
| 10 . devolva t[n, c] |
A matriz booleana t[0 .. n, 0 .. c] faz o papel da tabela de soluções de subinstâncias. O algoritmo usa uma ideia ampliada de subinstância: qualquer instância que tenha vetor de pesos p[1 .. i] e algum alvo em 0 .. c. No fim de cada execução do bloco de linhas 6-9,
t[i, j] é a solução da subinstância ( p, i, j) .
Para calcular t[i, j], o bloco de linhas 6-9 usa a recorrência ditada pela estrutura recursiva discutida na seção anterior:
| t[i, j] | = | t[i − 1, j] | se p[i] > j | |
| t[i − 1, j] ∨ t[i − 1, j − p[i]] | se p[i] ≤ j |
sendo ∨ o operador booleano ou.
Os valores iniciais da recorrência são t[i, 0] = 1
para todo i e t[0, j] = 0
para todo j ≥ 1.
(Observe que a recorrência só é possível porque os pesos e os alvos são números naturais.)
O algoritmo preenche a tabela por colunas
:
primeiro a coluna 0,
depois a coluna 1, etc.,
e finalmente a coluna c.
Cada coluna é preenchida de cima para baixo
,
ou seja, com i crescendo de 0 a n.
Desse modo, as casas [i−1, j] e [i−1, j−p[i]]
já estão preenchidas quando o valor de t[i, j]
começa a ser calculado.
Assim, no fim da linha 10,
t[n, c]
é a solução da instância original ( p, n, c) .
Exemplo C: Suponha que n = 4, c = 5 e o vetor de pesos p é dado pela figura esquerda. A figura direita representa a tabela t. (A tabela tem um erro que você deve descobrir.)
|
|
por colunas(a coluna 0, depois a coluna 1, etc.). Escreva uma variante do algoritmo que preencha a tabela
por linhas.
For every polynomial algorithm you have,
I have an exponential algorithm
that I would rather run.
— Alan Perlis
Quanto tempo o algoritmo Subset-Sum-Prog-Din consome? Cada execução da linha 9 do algoritmo Subset-Sum-Prog-Din preenche uma casa da tabela t[0 .. n, 0 .. c]. Entre uma execução da linha 9 e a execução seguinte, o algoritmo consome uma quantidade constante de tempo. Logo, o consumo total de tempo do algoritmo é proporcional ao tamanho da tabela. Como a tabela tem n+1 linhas e c+1 colunas, o consumo de tempo está em
Θ(n c) .
Para colocar em foco o efeito do alvo c, faça o seguinte experimento mental. Imagine que o alvo e os pesos são multiplicados por 1000. Esta operação é uma mera mudança de escala ou de unidades de medida (como mudar de kilogramas para gramas), e portanto a nova instância é conceitualmente idêntica à original. Apesar disso, o algoritmo consumirá 1000 vezes mais tempo para resolver a nova instância!
Nesse ponto, é preciso perguntar: qual a nossa definição de tamanho de uma instância do nosso problema? A expressão Θ(nc) dá a impressão de que o tamanho de uma instância é o par (n, c), ou, quem sabe, o produto n c. Mas essa definição não é razoável pois envolve o valor de c e não seu tamanho. O tamanho de c, ou seja, o número de dígitos de c, é cerca de log c. (O tamanho de 100000, por exemplo, é 6.) O consumo de tempo deveria, portanto, ser escrito como
Θ( n 10log c ) .
ou, equivalentemente, Θ( n 2lg c ) . O algoritmo Subset-Sum-Prog-Din é, portanto, exponencial no tamanho das instâncias do problema (exceto se nos restringirmos às instâncias em que c ≤ 100 n, por exemplo). Note que o algoritmo é exponencial por razões inerentes ao problema e não por alguma deficiência do método de programação dinâmica.
A propósito, não se descobriu ainda um algoritmo para o problema subset sum que seja substancialmente mais rápido que o de programação dinâmica.
| Algo (n) |
| 1 . s := 0 |
| 2 . para i := 1 até n |
| 3 .ooo s := s + i |
|
4
.
devolva s |
10por seu expoente favorito.)
10por seu expoente favorito.)