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 editar

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 editar

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 editar

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(ixj, 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 ixj, uma vez que xj + subconjunto da soma = i.

Notas editar

Erro de citação: Elemento <ref> com nome "knapsack" definido em <references> não é utilizado no texto da página.

Referências editar