Problema da partição
Na ciência da computação, o problema da partição (ou particionamento de números[1]) é a tarefa de decidir se um determinado multiconjunto S de números inteiros positivos pode ser particionado em dois subconjuntos de S1 e S2 , tais que a soma dos números em S1 é igual à soma dos números em S2. Embora o problema da partição seja NP-completo, existe uma solução com programação dinâmica com tempo pseudo-polinomial e há uma heurística que resolve o problema, em muitos casos, de forma otimizada, ou aproximadamente. Por esta razão, ele tem sido chamado de "o problema NP-difícil mais fácil".[2]
Há uma versão otimizada do problema da partição, que é particionar o multiconjunto S em dois subconjuntos S1, S2 , tais que a diferença entre a soma dos elementos de S1 e a soma dos elementos de S2 é minimizada. A versão de otimização é NP-difícil, mas pode ser resolvida de forma eficiente na prática.[3]
Exemplos
Dado S = {3,1,1,2,2,1}, uma solução válida para o problema da partição é formada pelos dois conjuntos S1 = {1,1,1,2} e S2 = {2,3}. Ambos os conjuntos a soma é de 5, e eles são partições de S. Note que esta solução não é única. S1 = {3,1,1} e S2 = {2,2,1} é outra solução.
Nem todos os multiconjuntos de números inteiros positivos tem uma partição em duas metades, com igual soma. Um exemplo de um conjunto S = {2,5}.
Algoritmo de tempo pseudo-polinomial
O problema pode ser resolvido usando programação dinâmica quando o tamanho do conjunto e o tamanho da soma dos números inteiros no conjunto não é muito grande para tornar os requisitos de armazenamento inviável.
Suponha que a entrada para o algoritmo seja uma lista com a seguinte forma:
- S = x1, ..., xn
Seja N o número de elementos de S. Seja K a soma de todos os elementos de S. Ou seja: K = x1 + ... + xn. Vamos construir um algoritmo que determina se existe um subconjunto de S cuja soma é . Se existe um subconjunto, em seguida:
- se K é par, o resto de S também tem soma
- se K é ímpar, então o resto de S tem soma . Esta é uma boa solução possível.
Relação de recorrência
Desejamos determinar se existe um subconjunto de S que tem soma (. Seja:
- p(i, j) é Verdadeiro se um subconjunto de { x1, ..., xj } tem soma i e False caso contrário.
Então p(, n) é Verdadeira se, e somente se, existe um subconjunto de S cuja soma é . O objetivo do nosso algoritmo será para calcular p(, n). Para isso, temos a seguinte relação de recorrência:
- p(i, j) é Verdadeiro se qualquer p(i, j − 1) é Verdadeira ou se p(i − xj, j − 1) é Verdadeiro
- p(i, j) é Falso caso contrário
A razão para isso é a seguinte: existe algum subconjunto de S que tem soma i utilizando números
- x1, ..., xj
se e somente se uma das seguintes condições for verdadeira:
- Existe um subconjunto de { x1, ..., xj-1 } que tem soma i;
- existe um subconjunto de { x1, ..., xj-1 } que tem soma i − xj, uma vez que xj + subconjunto da soma = i.