Esta página discute o problema
subset-sum, também conhecido como exact subset-sum.
Trata-se de um caso especial
do problema da mochila booleana.
Poderíamos chamar o problema de soma de subconjunto
,
mas é melhor usar o nome tradicional em inglês.
O problema é mencionado nas seções 34.5.5 e 35.5 do CLRS. Veja também a seção 6.1 de KT. Veja ainda o verbete Subset sum problem na Wikipedia.
Dados números p1, p2, … , pn e um subconjunto X de {1,2,…,n}, denotaremos por p(X) a soma ∑i∈X pi . Considere o seguinte problema:
Problema subset-sum: Dados números naturais p1, p2, … , pn e c, decidir se existe um subconjunto X de {1,2,…,n} tal que p(X) = c.
Diremos que os números
p1,p2,…,pn
são os pesos
e c
é a capacidade
do problema.
(A ordem em que os pesos são dados é, obviamente, irrelevante.)
O problema só admite duas soluções,
sim
e não
,
que podemos representar por 1 e 0 respectivamente.
Alguns exemplos:
simpois o conjunto {2,4} tem a propriedade desejada. O conjunto {1,4,5} também tem a propriedade desejada.
simse e somente se c vale 0.
cabe no espaço disponível, então acrescente i à solução X; senão, ignore i. Descreva esta heurística em pseudocódigo. Mostre que a heurística não resolve o problema. Repita o exercício supondo que os pesos pi estão em ordem crescente. Repita supondo que os pesos estão em ordem decrescente.
Como mostraremos a seguir, o problema tem estrutura recursiva, ou seja, toda solução de uma instância é composta por soluções de suas subinstâncias.
Seja (p1,p2,…,pn, c) uma instância do problema. Seja X um subconjunto de {1,2,…,n} tal que p(X) = c. Temos duas possibilidades: X contém n ou não contém n. No segundo caso, X é solução da subinstância
(p1,p2,…,pn−1, c)
No primeiro caso, X−{n} é solução da subinstância
(p1,p2,…,pn−1, c−pn).
(É claro que esta segunda alternativa só faz sentido se pn ≤ c.) Essa estrutura recursiva leva imediatamente ao seguinte algoritmo, que devolve 1 ou 0 conforme exista ou não um conjunto X tal que p(X) = c:
Subset-Sum-Rec (p, n, c) |
11 o se n = 0 |
12 oooo então se c = 0 |
13 oooo então ooo então devolva 1 |
14 oooo então ooo senão devolva 0 |
15 oooo senão s ← Subset-Sum-Rec (p, n−1, c) |
16 oooo senão se s = 0 e pn ≤ c |
17 oooo senão ooo então s ← Subset-Sum-Rec (p, n−1, c−pn) |
18 oooo senão devolva s |
O consumo de tempo do algoritmo é proporcional ao número de invocações de Subset-Sum-Rec. (Alternativamente, poderíamos medir o consumo de tempo pelo número de comparações de c com um componente de p na linha 6.) Seja T(n) esse número de invocações no pior caso. Então T(0) = 0 e
T(n) = 2 + T(n−1) + T(n−1)
se n ≥ 1. A solução dessa recorrência é T(n) = 2n+1−2. Assim, o consumo de tempo está em Ο(2n). O consumo de tempo também está em
Ω(2n)
no pior caso, o que torna o algoritmo inútil exceto para valores muito pequenos de n.
A cota inferior exponencial não surpreende
pois, no pior caso,
o algoritmo examina todos os 2n subconjuntos
de {1,…,n}.
Pode-se dizer que Subset-Sum-Rec
é um algoritmo de enumeração implícita
.
(Note porém que o espaço de trabalho
usado pelo algoritmo
é apenas Ο(n),
pois a pilha de recursão
nunca tem mais que 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−p4)−p2).)
For every polynomial algorithm you have,
I have an exponential algorithm that I would rather run.
— Alan Perlis
O algoritmo Subset-Sum-Rec é ineficiente porque recalcula várias vezes, sem necessidade, a solução de algumas das instâncias do problema. O remédio é usar a técnica da programação dinâmica e guardar as soluções das (sub)instâncias em uma tabela. A tabela, digamos t, é definida assim:
t[i,b]
é a solução (0 ou 1)
da instância
(p1,…,pi, b)
do problema.
Os possíveis valores de i são 0,1,…,n e os possíveis valores de b são 0,1,…,c (pois p1,…,pn e c são números naturais). Para todo i ≥ 1 teremos
t[i,b] | = | t[i−1,b] | se pi > b e | |
t[i−1,b] ∨ t[i−1,b−pi] | se pi ≤ b |
(onde ∨ é o operador lógico OU).
Essa recorrência decorre da estrutura recursiva do problema.
É fácil usar a recorrência
para calcular a tabela t:
basta preencher as casas da tabela de
da esquerda para a direita
(ou seja, para valores crescentes de i)
e de cima para baixo
(ou seja, para valores crescentes de b).
Desse modo,
as casas (i−1,b) e
(i−1,b−pi)
já estarão preenchidas quando
o algoritmo começar a cuidar da casa (i,b).
Subset-Sum-Prog-Din (p, n, c) |
11 .o para i crescendo de 0 até n faça |
12 .oooo t[i,0] ← 1 |
13 .o para b crescendo de 1 até c faça |
14 .oooo t[0,b] ← 0 |
15 .oooo para i crescendo de 1 até n faça |
16 .ooooooo s ← t[i−1,b] |
17 .ooooooo se s = 0 e pi ≤ b |
18 .oooooooooo então s ← t[i−1,b−pi] |
19 .ooooooo t[i,b] ← s |
10 .o devolva t[n,c] |
Exemplo: Suponha que n = 4, c = 5 e o vetor p é dado pela figura esquerda. Então, a figura direita representa a tabela t. (A tabela tem um erro que você deve descobrir.)
|
|
O consumo de tempo do algoritmo Subset-Sum-Prog-Din é proporcional ao tamanho da tabela t. Como a tabela tem n+1 linhas e c+1 colunas, o algoritmo consome Ο(nc) unidades de tempo, mesmo no pior caso. (A estimativa é justa, pois o algoritmo consome Ω(nc) unidades de tempo em todos os casos.)
Para colocar em foco o efeito de c sobre o consumo de tempo, faça o seguinte experimento mental. Imagine que os números p1,…,pn e c são multiplicados por 100. Esta operação é uma mera mudança de escala, e portanto a nova instância é conceitualmente idêntica à original. Apesar disso, o algoritmo consumirá 100 vezes mais tempo para resolver a nova instância.
O algoritmo Subset-Sum-Prog-Din não pode portanto ser considerado rápido. (Em linguagem técnica, o algoritmo é exponencial.) Infelizmente, não se descobriu ainda um algoritmo substancialmente melhor.
por colunas(a primeira coluna, depois a segunda, etc.). Escreva uma variante do algoritmo que preencha a tabela
por linhas.
Há uma generalização muito natural e útil do problema subset-sum:
Problema subset-sum generalizado: Dados números naturais p1, p2, … , pn e c, encontrar um subconjunto X de {1,2,…,n} que maximize p(X) sob a restrição p(X) ≤ c.
(Imagine um armazém com uma grande quantidade de caixas de pesos variados. Para transportar essas caixas, tenho um caminhão com capacidade para c toneladas. Quero embarcar a maior carga possível no caminhão.)
É claro que qualquer algoritmo para o problema generalizado pode ser usado para resolver o nosso problema subset-sum básico.
rodaro software?
SubSumG (S, c) |
1 .o se c ≤ 1 |
2 .oooo então ((use força bruta)) |
3 .oooo senão X ← SubSumG (S, ⌊c/2⌋) |
4 .oooo senão Y ← SubSumG (S, ⌈c/2⌉) |
5 .oooo senão devolva X ∪ Y |