Une variante du problème du sac à dos: comment résoudre le problème de la somme des sous-ensembles égaux de partition en Java

Auparavant, j'ai écrit sur la résolution du problème du sac à dos (KP) avec la programmation dynamique. Vous pouvez lire à ce sujet ici.

Aujourd'hui, je veux discuter d'une variante de KP: le problème de la somme des sous-ensembles égaux de partition. J'ai vu ce problème pour la première fois sur Leetcode - c'est ce qui m'a poussé à en savoir plus et à écrire sur KP.

Voici l'énoncé du problème (reproduit partiellement sans exemples):

Étant donné un tableau non vide contenant uniquement des entiers positifs, recherchez si le tableau peut être partitionné en deux sous-ensembles de sorte que la somme des éléments des deux sous-ensembles soit égale.

Pour l'énoncé complet du problème, avec des contraintes et des exemples, consultez le problème Leetcode.

Programmation dynamique

Comme avec KP, nous allons résoudre ce problème en utilisant la programmation dynamique. Puisqu'il s'agit d'une variante de KP, la logique et la méthodologie sont largement similaires.

Solution

Nous hébergerons notre solution dans une méthode qui retourne un booléen - true si le tableau peut être partitionné en sous-ensembles égaux, et false dans le cas contraire.

Étape 1: se prémunir contre une somme de tableau impaire

Trivialement, si tous les nombres du tableau s'additionnent à une somme impaire, nous pouvons renvoyer false. Nous ne procédons que si le tableau s'additionne à une somme paire.

Étape 2: création du tableau

Ensuite, nous créons la table.

Les lignes du tableau représentent l'ensemble des éléments du tableau à prendre en compte, tandis que les colonnes du tableau indiquent la somme à laquelle nous voulons arriver. Les valeurs de table sont simplement des valeurs booléennes, indiquant si une somme (colonne) peut être obtenue avec un ensemble d'éléments de tableau (ligne).

Concrètement, la ligne i représente un ensemble d'éléments du tableau d'indices 0 à ( i -1). La raison de ce décalage de 1 est que la ligne 0 représente un ensemble vide d'éléments. Par conséquent, la ligne 1 représente le premier élément du tableau (index 0), la ligne 2 représente les deux premiers éléments du tableau (indices 0–1), et ainsi de suite. Au total, nous créons des n + 1lignes, y compris 0.

Nous voulons seulement savoir si nous pouvons résumer exactement la moitié de la somme totale du tableau. Nous n'avons donc besoin que de créer des totalSum / 2 + 1colonnes, y compris 0.

Étape 3: pré-remplissage de la table

Nous pouvons immédiatement commencer à remplir les entrées pour les cas de base dans notre tableau - ligne 0 et colonne 0.

Dans la première ligne, chaque entrée - sauf la première - doit être false. Rappelez-vous que la première ligne représente un ensemble vide. Naturellement, nous ne pouvons arriver à aucune somme cible - numéro de colonne - sauf 0.

Dans la première colonne, chaque entrée doit être true. Nous pouvons toujours, trivialement, arriver à une somme cible de 0, quel que soit l'ensemble des éléments avec lesquels nous devons travailler.

Étape 4: Construire la table (le nœud du problème)

Certaines entrées du tableau à la ligne i et à la colonne j sont true(réalisables) si l'une des trois conditions suivantes est remplie:

  1. l'entrée à la ligne i -1 et à la colonne j est true. Rappelez-vous ce que représente le numéro de ligne. Par conséquent, si nous pouvons atteindre une somme particulière avec un sous-ensemble des éléments que nous avons actuellement, nous pouvons également atteindre cette somme avec notre ensemble actuel d'éléments - en n'utilisant tout simplement pas les éléments supplémentaires. C'est trivial. Appelons ça prevRowIsTrue.
  2. L'élément actuel est exactement la somme que nous voulons atteindre. C'est aussi trivialement vrai. Appelons ça isExactMatch.
  3. Si les deux conditions ci-dessus ne sont pas satisfaites, il nous reste un moyen d'atteindre notre somme cible. Ici, nous utilisons l'élément courant - l'élément supplémentaire dans l'ensemble des éléments de notre ligne actuelle par rapport à l'ensemble des éléments de la ligne précédente - et vérifions que nous sommes en mesure d'atteindre le reste de la somme cible. Appelons ça canArriveAtSum.

Décompressons la condition 3. Nous ne pouvons utiliser l'élément courant que s'il est inférieur à notre somme cible. S'ils sont égaux, la condition 2 serait satisfaite. S'il est plus grand, nous ne pouvons pas l'utiliser. Par conséquent, la première étape consiste à s'assurer que l'élément actuel <somme cible.

Après avoir utilisé notre élément actuel, nous nous retrouvons avec le reste de notre somme cible. Nous vérifions ensuite si cela est réalisable en vérifiant l'entrée correspondante dans la ligne ci-dessus.

Comme pour KP classique, nous voulons construire progressivement notre table de bas en haut. Nous commençons par les cas de base, jusqu'à ce que nous arrivions à notre solution finale.

Étape 5: Renvoyer la réponse

Nous revenons simplement return mat[nums.length][totalSum / 2].

Code de travail

Merci d'avoir lu!