Trouver la taille maximale possible de S, où S est un ensemble de sous-ensembles par paires de la liste, et chaque élément de S à K

Question

Disons que j'avais une liste de nombres dans la plage de 1-20 par exemple: [5, 16, 17, 3, 2, 14, 4, 9, 11, 19], et un entier K (disons k = 40)

Comment trouver la taille maximale possible de S, où S est un ensemble de sous-ensembles par paires de la liste, et chaque élément de S à K?

Je crois que cet algorithme est complet NP.

Considérez simplement le problème comme un algorithme d'emballage de bacs mais au lieu de dire que la valeur totale des articles dans le bac ne doit pas dépasser la capcacité du bac, je dis que la valeur totale des articles dans le bac doit être exactement égale à la capacité du bac . De plus, nous essayons de maximiser le nombre de bacs.

Exemple de scénario:

Disons que j'ai une liste: [1, 2, 2, 3, 5, 6, 5] et k = 7, alors quelques exemples de valeurs de S seraient:

(3 + 2 + 2), (6 + 1)] - 5 et 5 à gauche

(5 + 2), (5 + 2), (6 + 1)] - 3 à gauche

Comme vous pouvez le voir, la deuxième solution est optimale car elle produit 3 partitions plutôt que 2.