Início / coding / Perguntas / 79564757
Accepted
Samuel Bismuth
Asked: 2025-04-09 23:42:25 +0800 CST

Obtendo todos os subconjuntos distintos do problema de soma de subconjuntos com alvo T usando programação dinâmica

  • 772

No problema clássico de soma de subconjuntos, há um conjunto S e um alvo t, e o objetivo é encontrar um subconjunto de S cuja soma seja t. Esta variante tem uma solução em tempo pseudopolinomial.

Em uma variante do problema da soma de subconjuntos, o objetivo é encontrar todos os subconjuntos de S cuja soma é t. Esta variante não possui solução em tempo pseudopolinomial; veja as respostas aqui: Obtendo todos os subconjuntos do problema da soma de subconjuntos em Python usando Programação Dinâmica . Um dos comentários explica que, no pior caso, quando você tem N zeros e a soma necessária também é zero, você precisará gerar todos os 2^n - 1 subconjuntos - portanto, não é possível obter um resultado melhor que O(2^n).

E se não diferenciarmos entre dois itens do mesmo valor (de modo que, se dois conjuntos forem compostos de alguns itens com os mesmos valores, eles serão considerados o mesmo conjunto) --- qual é a complexidade de tempo de execução para gerar todos os diferentes subconjuntos com soma t?

algorithm

2 respostas

  1. Best Answer

    Acredito que o pior caso para o seu problema revisado é que o conjunto seja composto por todos os inteiros de -ma m, buscando uma soma de 0. Este conjunto não possui nenhuma duplicata.

    Neste caso n = 2m+1, como ne mvariam por um fator constante, eles são os mesmos no que diz respeito ao big-O.

    A maior soma possível é m*(m+1)/2e a menor é -m*(m+1)/2. Isso significa que os 2^nsubconjuntos possíveis são divididos entre O(n^2)somas possíveis. Isso cria um limite inferior imediato de O(2^n / n^2), que é exponencial.

    Esse limite inferior pode ser ligeiramente melhorado usando o teorema do limite central. Considere o caso de um conjunto aleatório. Ele é a soma de nvariáveis ​​aleatórias. Cada variável aleatória tem alguma média ie variância (i/2)^2. A soma das variáveis ​​aleatórias tem média 0e variância O(n^3). Portanto, é aproximadamente uma distribuição normal com média 0e desvio padrão que é O(n^(3/2)). O que significa que o número de maneiras de somar 0deve ser O(2^n / n^(3/2)).

    • 1

  2. No pior caso, quando você tem N zeros e a soma necessária também é zero, você precisa gerar N conjuntos diferentes com 1, 2, 3, ... N zeros. Então O(n)

    • 0

relate perguntas