Problème de partition

Une définition formelle du problème de décision est la suivante: Étant donné un multiensemble ${\displaystyle S}$ de n nombres entiers positifs. On cherche deux sous-multiensembles ${\displaystyle S_{1}}$ et ${\displaystyle S_{2}}$ de telle sorte que ${\displaystyle S_{1}\uplus S_{2}=S}$ et ${\displaystyle E=0}$. On définit ${\displaystyle E}$ comme ceci :

${\displaystyle E=\left|\sum _{x\in S_{1}}x-\sum _{y\in S_{2}}y\right|}$

Si ${\displaystyle E}$ est nul, alors la somme des éléments de ${\displaystyle S_{1}}$ est égale à la somme des éléments de ${\displaystyle S_{2}}$ et une solution au problème existe pour ${\displaystyle S}$.

Par exemple, on peut partitionner le multiensemble {3,1,1,2,2,1} en {1,1,1,2} et {2,3}, puisque la somme de leurs éléments est égale (1 + 1 + 1 + 2 = 5 ainsi que 2 + 3 = 5). Pour le multiensemble {7,3,1,7}, il n'est pas possible de trouver deux sous-multiensembles qui respectent la contrainte.

Pour prouver que le problème de partition appartient à la classe des problèmes NP-complets, il faut montrer que ce problème est dans NP et qu'il est NP-difficile.

 fonction verifie_partition(ens1, ens2)
    tailleEns1 = taille(ens1) - 1
    tailleEns2 = taille(ens2) - 1
    cptEns1 = 0
    cptEns2 = 0
    pour i = 0 à tailleEns1
        cptEns1 = cptEns1 + ens1[i]
    pour j = 0 à tailleEns2
        cptEns2 = cptEns2 + ens2[j]
    si cptEns1 == cptEns2
        retourne vrai
    sinon
        retourne faux

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Partition problem » (voir la liste des auteurs).
• (nl) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en néerlandais intitulé « Partitieprobleem » (voir la liste des auteurs).