| Wikipédia em português - A enciclop... |
Problema da soma dos subconjuntos
Em ciências da computação, o problema da soma de subconjuntos é um importante problema da teoria da complexidade computacional e criptografia. O problema é este: dado um conjunto de inteiros, existe um subconjunto não-vazio cuja soma é 0? Por exemplo, dado o conjunto { -7, -3, -2, 5, 8}, a resposta é sim porque o subconjunto { -3, -2, 5} resulta numa soma que dá zero. O problema é NP-completo.
Um problema equivalente é este: dado um conjunto de inteiros e um inteiro s, existe algum subconjunto que some s? Problema da soma dos subconjuntos também pode ser pensado como um caso especial do problema da mochila. Um caso interessante de soma subconjunto é o problema de partição, em que s é a metade da soma de todos os elementos do conjunto.
| Veja mais na Wikipédia.org... |
© Esse artigo usa material da Wikipédia® sob a licença Licença GNU de Documentação Livre e sob nos termos da licença Creative Commons Attribution-ShareAlike
