O problema subset-sum
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.
O problema
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 de decisão:
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:
-
A instância do problema definida por
p = (30, 40, 10, 15, 10, 60, 54)
e
c = 55
tem solução "sim"
pois o conjunto {2,4} tem a propriedade desejada.
O conjunto {1,4,5} também tem a propriedade desejada.
-
O problema faz sentido mesmo quando n é 0.
Uma instância com n = 0
tem solução "sim" se e somente se
c vale 0.
-
O problema dos cheques:
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
na sua conta.
Você quer saber se algum conjunto de cheques corresponde ao valor debitado.
Exercícios
-
Problema:
dados números naturais
p1,p2,…,pn
e
c,
decidir se existem i ≠ j
tais que
pi + pj = c.
Escreva um algoritmo que resolva o problema em
Θ(n lg n)
unidades de tempo.
-
Discuta a relação entre o problema subset-sum e o seguinte problema:
dada uma sequência A[1..n]
de números naturais e um número natural c,
decidir se existe uma subsequência
B[1..k] de A[1..n]
tal que
B[1]+B[2]+…+B[k] = c.
-
Mostre que o objetivo do problema subset-sum pode ser formulado assim:
encontrar números
x1,
… ,
xn,
todos em {0,1},
tais que
x1p1 +
… +
xnpn = c .
-
Alguns livros formulam o problema assim:
dado um número natural c
e um conjunto A de números naturais,
encontrar um subconjunto B de A tal que
∑ B = c.
Qual a diferença entre esta formulação
e nossa formulação oficial?
Qual é mais geral?
Qual é mais fácil?
-
Considere o seguinte problema da soma de segmento:
dados números naturais
p1,…,pn
e
c,
encontrar índices i e k
tais que
1 ≤ i ≤ k ≤ n
e
pi+…+pk
=
c.
Este problema é um caso especial do subset-sum?
-
[Heurística gulosa]
Considere a seguinte heurística gulosa
para o problema subset-sum.
Para i = 1,2,…n,
se pi
"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.
-
[Redução entre problemas]
Suponha que você recebeu de presente um programa muito rápido
para o problema subset-sum.
Como é possível usar esse programa
(sem olhar o seu código)
para encontrar um
subconjunto X de {1,2,…,n}
tal que
p(X) = c?
Quantas vezes é preciso executar o programa?
A estrutura recursiva do problema
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.)
Exercícios
-
Prove que o problema de fato tem a estrutura recursiva descrita acima.
-
Mostre que a pilha de recursão do algoritmo
Subset-Sum-Rec
nunca tem mais que n elementos.
-
Mostre que, no pior caso, o algoritmo
Subset-Sum-Rec
examina todos os subconjuntos de {1,…,n}.
(Sugestão:
Imagine uma instância com resposta "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).)
-
Mostre que o algoritmo Subset-Sum-Rec
pode recalcular várias vezes
a solução de uma mesma instância do problema.
(Sugestão:
Suponha que
pn = pn−1.
Então as instâncias
(n−2, c−pn)
e
(n−2, c−pn−1)
são idênticas.)
-
Escreva um algoritmo iterativo que resolva o problema subset-sum
por enumeração explícita de todos os subconjuntos de {1,…n}.
(Sugestão:
Represente cada subconjunto de {1,…,n}
por um vetor de bits
(b1,…,bn).
Gere cada vetor de bits a partir do anterior
como se estivesse somando 1 em notação binária.)
Mostre que o seu algoritmo consome tempo Ο(2n)
e espaço Ο(n).
-
[Algoritmo 1.415^n]
Suponha que
p(X) = c
para algum X ⊆ {1,…,n}.
Seja Y o conjunto
{i ∈ X : i ≤ n/2}
e
Z o conjunto
{i ∈ X : i > n/2}.
Então
p(Y) =
c − p(Z) .
Esta observação leva ao seguinte algoritmo:
-
Seja m o piso
de n/2.
Seja A o conjunto {1,…,m}
e B o conjunto {m+1,…,n}.
-
Sejam
A1,
A2,
…,
A2m
todos os subconjuntos de A.
Para k = 1,…,2m,
seja s[k] o número
c − p(Ak).
-
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 pseudocódigo.
Analise o consumo de tempo do algoritmo.
Analise o consumo de espaço.
Algoritmo de programação dinâmica
"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.)
|
|
|
|
| 0
| 1
| 2
| 3
| 4
| 5
|
| 0
| 1
| 0
| 0
| 0
| 0
| 0
|
| 1
| 1
| 0
| 0
| 0
| 1
| 0
|
| 2
| 1
| 0
| 1
| 0
| 1
| 0
|
| 3
| 1
| 1
| 1
| 1
| 0
| 1
|
| 4
| 1
| 1
| 1
| 1
| 1
| 1
|
|
Desempenho do algoritmo
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.
Exercícios
-
Se tivesse que programar
Subset-Sum-Prog-Din
pra valer,
que comentários você escreveria junto com o código?
[Solução]
-
O algoritmo Subset-Sum-Prog-Din
preenche a tabela t "por colunas"
(a primeira coluna, depois a segunda, etc.).
Escreva uma variante do algoritmo que preencha a tabela
"por linhas".
-
Discuta a seguinte ideia.
Seja d o máximo divisor comum de
p1,p2,…,pn
e c.
Submeta ao algoritmo Subset-Sum-Prog-Din
a instância
(p1/d,
p2/d,
… ,
pn/d,
c/d)
do problema.
-
[CLR 36.1-4, CLRS 34.1-4]
O algoritmo Subset-Sum-Prog-Din
é polinomial?
-
Escreva uma variante do algoritmo Subset-Sum-Prog-Din
que devolva um conjunto X tal que
p(X) = c.
Se tal X não existe, o seu algoritmo deve parar sem nada devolver.
-
[Desafio]
Descubra um algoritmo que resolva o problema subset-sum
em tempo Ο(n4).
-
[Desafio]
Descubra um algoritmo que resolva o problema subset-sum em tempo
Ο(d3),
sendo d o número total de dígitos decimais de
p1,…,pn
e c.
Problema subset-sum generalizado
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.
Exercícios
-
Discuta a relação entre o problema subset-sum generalizado
e o seguinte problema:
Dados números naturais
p1,p2,…,pn
e c,
encontrar o maior número b em {0,1,…,c}
tal que p(X) = b
para algum subconjunto X de {1,2,…,n}.
-
Mostre como um algoritmo para o
problema subset-sum generalizado
pode ser usado para resolver o nosso
problema subset-sum básico.
-
Modifique o algoritmo Subset-Sum-Rec
para resolver o problema subset-sum generalizado.
-
Modifique o algoritmo 1.415^n
sugerido acima
para resolver o problema subset-sum generalizado.
-
Modifique o algoritmo Subset-Sum-Prog-Din
para resolver o problema subset-sum generalizado.
-
Dados números naturais
p1,…,pn
e c,
queremos encontrar números
x1,…,xn
em {0,1} que maximizem
x1p1+…+xnpn
sob a restrição
x1p1+…+xnpn ≤ c.
Mostre que esse problema é idêntico ao problema subset-sum generalizado.
Por que não usar um algoritmo de
programação linear
para resolver o problema?
-
[Redução entre problemas]
Suponha que você ganhou de presente um software muito rápido
para o problema subset-sum.
Eu gostaria de usar o software
(sem olhar o seu código)
para resolver o problema subset-sum generalizado.
Como é possível fazer isso?
Quantas vezes é preciso "rodar" o software?
-
Seja S um conjunto de números naturais
e c um número natural.
Queremos encontrar um subconjunto X de S
que maximize ∑X sob a restrição
∑X ≤ c.
Discuta o seguinte algoritmo para o problema:
|
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
|
