Subset sum

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.

O problema

Dado um vetor númerico p[1 .. n] e um subconjunto X de {1, 2, … , n}, denotaremos por  p(X)  a soma  iX 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
 
 

Exercícios 1

  1. Qual a solução da instância do problema subset sum que tem pesos (6, 6, 3, 5, 6, 3, 2) e alvo 13? Repita o exercício com pesos (5, 6, 3, 5, 3, 6) e alvo 7.
  2. Mostre uma família não trivial de instâncias do problema subset sum que têm solução não.
  3. 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. Discuta a relação entre esse problema e o problema subset sum.
  4. Mostre que o problema subset sum pode ser formulado assim: encontrar um vetor x[1 .. n] com elementos em {0, 1} tal que x[1] p[1] + ⋯+ x[n] p[n] = c.
  5. ★ Alguns livros formulam o problema subset sum 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?
  6. ★ O seguinte problema é vagamente semelhante ao problema subset sum: dado um vetor p[1 .. n] de números naturais e um número natural c, decidir se existem i ≠ j tais que  p[i] + p[j] = c. Escreva um algoritmo que resolva o problema em Θ(n lg n) unidades de tempo.
  7. Problema da soma de segmento. Dado um vetor p[1 .. n] de números naturais e um número natural c, encontrar índices i e k tais que 1 ≤ ikn e p[i] + ⋯ + p[k] = c. Este problema é um caso especial do subset-sum?
  8. Heurística gulosa.  Considere a seguinte heurística gulosa para o problema subset sum. Para i = 1, 2, … , n, se p[i] é menor ou igual ao alvo, então acrescente i ao subconjunto X e subtraia p[i] do alvo; senão, ignore i. Descreva esta heurística em código. Mostre que a heurística não resolve o problema.  Repita o exercício supondo que os pesos p[i] estão em ordem crescente. Repita supondo que os pesos estão em ordem decrescente.
  9. Redução entre problemas.  Suponha que você recebeu de presente um programa para o problema subset sum, ou seja, um programa que decide se existe um subconjunto X de {1, 2, … , n} tal que p(X) = c. Como é possível usar esse programa (sem olhar 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

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
 40 
 
 1..2 
 40 
   1..2 
 10 

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.

Exercícios 2

  1. ★ Prove a estrutura recursiva descrita acima. [Solução]
  2. Execute o algoritmo Subset-Sum-R com argumentos p = (95, 85, 91, 93) e c = 179. Faça o rastreamento da execução. Use uma árvore binária para representar a recursão.
  3. ★ Seja T a função definida pela recorrência T(n) = 3 + 2 T(n−1) com valor inicial T(0) = 3. Prove que T(n) = Θ(2n).
  4. Enumeração implícita.  Mostre que, no pior caso, o algoritmo Subset-Sum-R 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, (cp[4])−p[2]).)
  5. Mostre que a pilha de recursão do algoritmo Subset-Sum-R nunca tem mais que n elementos.
  6. Algoritmo 1.415^n.  Suponha que p(X) = c para algum subconjunto X de { 1, … , n }. Seja Y o conjunto { iX : in/2 } e Z o conjunto { iX : i > n/2 }. Então p(Y) = c − p(Z). Esta observação leva ao seguinte algoritmo para o problema subset sum:

    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.

  7. Quantas unidades de tempo o algoritmo Subset-Sum-R consome para processar uma instância de tamanho n = 100?

Algoritmo de programação dinâmica

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[ij] é 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[ij] = 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, jp[i]] já estão preenchidas quando o valor de t[i, j] começa a ser calculado. Assim, no fim da linha 10, t[nc] é 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.)

  1 2 3 4
p 4 2 1 3
 
  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 1 0
4 1 1 1 1 1 1

Exercícios 3

  1. Use o algoritmo Subset-Sum-Prog-Din para resolver a instância do problema subset sum que tem pesos (6, 6, 3, 5, 6, 3, 2) e alvo 13? Repita o exercício com pesos (5, 6, 3, 5, 3, 6) e alvo 7.
  2. Considere a tabela de programação dinâmica t[0 .. n, 0 .. c]. Suponha que t[i, j] = 1 para algum ij. Qual o valor de t[i, k] para k > j?
  3. Considere a tabela de programação dinâmica t[0 .. n, 0 .. c]. Suponha que p[i] ≥ 50 para todo i. Qual o conteúdo das primeiras 50 colunas da tabela?
  4. Por que não é uma boa ideia exigir que cada p[i] seja diferente de zero? Por que não é conveniente restringir a tabela t às linhas 1 .. n e às colunas 1 .. c?
  5. Se tivesse que programar Subset-Sum-Prog-Din pra valer, que comentários você escreveria junto com o código?
  6. ★ O algoritmo Subset-Sum-Prog-Din preenche a tabela t por colunas (a coluna 0, depois a coluna 1, etc.). Escreva uma variante do algoritmo que preencha a tabela por linhas.
  7. Reconstrução de um conjunto de peso c.  Considere a tabela t[0 .. n, 0 .. c] construída por Subset-Sum-Prog-Din. Escreva um algoritmo que use t para calcular um conjunto X tal que p(X) = c. O seu algoritmo deve devolver o vetor característico de X ou nada se tal X não existe.  (É uma boa ideia devolver o conjunto vazio, ∅, no caso em que não existe X tal que p(X) = c?)
  8. ★ 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, seu algoritmo deve parar sem nada devolver.

Desempenho da programação dinâmica

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

Θ(nc) .

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 nc. 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.

Exercícios 4

  1. Suponha que o algoritmo Subset-Sum-Prog-Din precisa de 6 (n + 1)(c + 1) unidades de tempo para preencher a tabela t. Mostre que 6 (n + 1)(c + 1) está em Θ(nc).
  2. Seja d o máximo divisor comum de c e dos elementos do vetor p[1 .. n]. Divida c e todos os elementos de p[1 .. n] por d. Submeta a nova instância do problema ao algoritmo Subset-Sum-Prog-Din. Discuta essa ideia.
  3. Divisão de herança. Suponha que p1, … , pn são números naturais e seja N o conjunto {1, … , n}. Uma divisão equilibrada de N é um par ( J, K) de conjuntos tal que JK = N, JK = ∅, e p(J) = p(K). (Não digo que ( J, K) é uma partição de N apenas porque J ou K podem ser vazios.)  Escreva um algoritmo que receba p1, … , pn e encontre uma divisão equilibrada de {1, … , n} se tal existir.
  4. O algoritmo de programação dinâmica Subset-Sum-Prog-Din é polinomial?
  5. ★ Considere o problema de calcular a soma de todos os números naturais de 1 a n. Qual o tamanho de uma instância do probema? Qual o consumo de tempo do algoritmo Algo abaixo em função do tamanho das instâncias? Escreva um algoritmo polinomial que produza o mesmo resultado que Algo.
    Algo (n)
    1 . s := 0
    2 . para i := 1 até n
    3 .ooo s := s + i
    4 . devolva s
  6. Subset sum generalizado. Como um algoritmo para o problema subset sum poderia ser usado para resolver o seguinte problema? Dado um vetor p[1 .. n] de números naturais e números naturais kc, decidir se existe um subconjunto X de {1, 2, … , n} tal que k ≤ p(X) < c.
  7. Desafio.  Descubra um algoritmo que resolva o problema subset sum em Ο(n10) unidades de tempo, qualquer que seja c. (Você pode trocar 10 por seu expoente favorito.)
  8. Desafio.  Descubra um algoritmo que resolva o problema subset sum em Ο((n lg c)10) unidades de tempo. (Você pode trocar 10 por seu expoente favorito.)