Partage de technologie

【1.5】Solution de programmation dynamique pour partitionner des sous-ensembles à somme égale

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Problème


Vous recevez un tableau nums non vide contenant uniquement des entiers positifs. Veuillez déterminer si ce tableau peut être divisé en deux sous-ensembles afin que la somme des éléments des deux sous-ensembles soit égale.

2. Idée de solution 1

Solution de programmation dynamique

Ce problème ne peut pas être résolu à l'aide de l'algorithme de retour en arrière. Si la quantité de données est importante, le délai expirera. Nous pouvons utiliser la programmation dynamique.
Cette question détermine si la somme des éléments des deux parties est égale lorsque le tableau est divisé en deux parties. Nous devons d'abord calculer la somme de tous les éléments du tableau, puis déterminer si la somme est un nombre pair : si ce n'est pas un nombre pair, cela signifie qu'il ne peut pas être divisé en deux parties complètement égales, et il renverra faux directement.
S'il s'agit d'un nombre pair, il suffit de déterminer s'il existe des éléments dont la somme est égale à somme/2, alors le reste doit également être égal à somme/2, ce qui signifie que. nous pouvons diviser le tableau en deux parties avec des éléments égaux.
Le problème est alors très clair à ce stade. En supposant que somme/2 soit la capacité d’un sac à dos, il suffit de trouver certains éléments et de les mettre dans le sac à dos si la somme maximale des éléments dans le sac à dos est égale à la somme. /2, cela signifie que nous pouvons mettre le tableau Divide en deux parties égales. N'est-ce pas le problème classique du sac à dos 0-1 ? Le problème de base du sac à dos dans la série des problèmes de sac à dos peut être trouvé en détail. Je ne répéterai pas l'introduction ici. Nous recherchons sa formule de récursion, définissant dp[i][j] pour représenter la valeur maximale obtenue en mettant le i-ème élément dans un sac à dos de capacité j.
La valeur du i-ième élément est nums [i -1] :
Si nums [i -1]>j, cela signifie que la capacité du sac à dos n'est pas suffisante et que le i-ème élément ne peut pas être mis dedans, nous ne pouvons donc pas sélectionner le i-ème élément, alors
dp[i][j]=dp[i -1][j]；
Si nums [i -1]<=j, cela signifie que le jième élément peut être mis dans le sac à dos. On peut choisir de le mettre ou non, il suffit de prendre la valeur maximale. Si on le met, il occupera une partie du. capacité du sac à dos. La valeur maximale oui.
dp[i][j]=dp[i-1][j-nums[i-1]]+nums[i-1]
Si tu ne lâches pas
dp[i][j]=dp[i -1][j]；
Prendre le maximum des deux

La formule récursive finale et le code sont les suivants :

  1. #include <vector>
  2.  
  3. bool canPartition(std::vector<int>& nums) {
  4.     // 计算数组中所有元素的和
  5.     int sum = 0;
  6.     for (int num : nums) {
  7.         sum += num;
  8.     }
  9.     // 如果sum是奇数，说明数组不可能分成完全相等的两份
  10.     if ((sum & 1) == 1) {
  11.         return false;
  12.     }
  13.     // sum除以2
  14.     int target = sum >> 1;
  15.     int length = nums.size();
  16.     std::vector<std::vector<int>> dp(length + 1, std::vector<int>(target + 1, 0));
  17.     for (int i = 1; i <= length; ++i) {
  18.         for (int j = 1; j <= target; ++j) {
  19.             // 下面是递推公式
  20.             if (j >= nums[i - 1]) {
  21.                 dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
  22.             } else {
  23.                 dp[i][j] = dp[i - 1][j];
  24.             }
  25.         }
  26.     }
  27.     // 判断背包最大是否能存放和为target的元素
  28.     return dp[length][target] == target;
  29. }

On peut aussi écrire ainsi : Le tableau bidimensionnel dp est de type booléen. dp[i][j] indique si la somme des i premiers éléments du tableau peut former une somme de j. 0]=true, ce qui signifie que les 0 premiers éléments (c'est-à-dire aucun élément) peuvent former une somme de 0.code affiché comme ci-dessous

  1. #include <vector>
  2.  
  3. bool canPartition(std::vector<int>& nums) {
  4.     // 计算数组中所有元素的和
  5.     int sum = 0;
  6.     for (int num : nums) {
  7.         sum += num;
  8.     }
  9.     // 如果sum是奇数，说明数组不可能分成完全相等的两份
  10.     if ((sum & 1) == 1) {
  11.         return false;
  12.     }
  13.     // sum除以2得到target
  14.     int target = sum >> 1;
  15.     int length = nums.size();
  16.     std::vector<std::vector<bool>> dp(length + 1, std::vector<bool>(target + 1, false));
  17.     // base case
  18.     dp[0][0] = true;
  19.     for (int i = 1; i <= length; ++i) {
  20.         for (int j = 0; j <= target; ++j) {
  21.             // 递推公式
  22.             if (j >= nums[i - 1]) {
  23.                 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
  24.             } else {
  25.                 dp[i][j] = dp[i - 1][j];
  26.             }
  27.         }
  28.     }
  29.     // 返回能否找到和为target的子集
  30.     return dp[length][target];
  31. }

Nous voyons que lors du calcul du tableau bidimensionnel ci-dessus, la valeur actuelle n'est liée qu'à la ligne ci-dessus, nous pouvons donc la changer en unidimensionnelle. Notez que la deuxième boucle for doit être flashback, sinon la valeur précédente sera écrasée. et le résultat sera faux, regardez de plus près.
dp[j] = (dp[j] || dp[j - nombres [i - 1]]);
Vous pouvez comprendre que la valeur à la fin d'une même ligne dépend de la précédente. S'il ne s'agit pas d'un flashback, la valeur précédente est modifiée, ce qui entraînera une erreur dans le calcul de la suivante.Jetons un coup d'œil au code

  1. #include <vector>
  2.  
  3. bool canPartition(std::vector<int>& nums) {
  4.     // 计算数组中所有元素的和
  5.     int sum = 0;
  6.     for (int num : nums) {
  7.         sum += num;
  8.     }
  9.     // 如果sum是奇数，说明数组不可能分成完全相等的两份
  10.     if ((sum & 1) == 1) {
  11.         return false;
  12.     }
  13.     // sum除以2得到target
  14.     int target = sum >> 1;
  15.     int length = nums.size();
  16.     std::vector<bool> dp(target + 1, false);
  17.     // base case
  18.     dp[0] = true;
  19.     for (int i = 0; i < length; ++i) {
  20.         // 注意这里j要倒序
  21.         for (int j = target; j >= nums[i]; --j) {
  22.             // 递推公式
  23.             dp[j] = dp[j] || dp[j - nums[i]];
  24.         }
  25.     }
  26.     // 返回能否找到和为target的子集
  27.     return dp[target];
  28. }

3. Idée de solution 2

Solution d'algorithme DFS

Chaque élément peut être sélectionné ou non. Il suffit de déterminer si la somme des éléments dans toutes ses combinaisons possibles est égale à somme/2. On peut le considérer comme un arbre binaire. Le nœud enfant de gauche représente la sélection des éléments. L'élément actuel et le nœud enfant de droite représentent la sélection de l'élément actuel. Le nœud enfant indique que l'élément actuel n'est pas sélectionné, comme le montre la figure ci-dessous. Le nœud orange indique que l'élément actuel est sélectionné et le nœud bleu. indique que l'élément actuel n'est pas sélectionné.

Jetons d'abord un coup d'œil au code d'implémentation préliminaire

  1. #include <vector>
  2.  
  3. bool dfs(const std::vector<int>& nums, int target, int index) {
  4.     // target等于0，说明存在一些元素的和等于sum/2，直接返回true
  5.     if (target == 0) return true;
  6.     // 如果数组元素都找完了，或者target小于0，直接返回false
  7.     if (index == nums.size() || target < 0) return false;
  8.     // 选择当前元素和不选择当前元素两种情况
  9.     return dfs(nums, target - nums[index], index + 1) || dfs(nums, target, index + 1);
  10. }
  11.  
  12. bool canPartition(std::vector<int>& nums) {
  13.     // 计算数组中所有元素的和
  14.     int sum = 0;
  15.     for (int num : nums) sum += num;
  16.     // 如果sum是奇数，说明数组不可能分成完全相等的两份
  17.     if ((sum & 1) == 1) return false;
  18.     // 调用dfs函数
  19.     return dfs(nums, sum >> 1, 0);
  20. }

Mais malheureusement, parce que la quantité de calcul est trop importante, cela entraînera un délai d'attente de l'opération. Nous pouvons l'optimiser et examiner le code.

  1. #include <vector>
  2.  
  3. bool dfs(const std::vector<int>& nums, int index, int target, std::vector<std::vector<int>>& map) {
  4.     // target等于0，说明存在一些元素的和等于sum/2，直接返回true
  5.     if (target == 0) return true;
  6.     // 如果数组元素都找完了，或者target小于0，直接返回false
  7.     if (index >= nums.size() || target < 0) return false;
  8.     // 如果此子问题已经被计算过，直接返回结果
  9.     if (map[index][target] != -1) return map[index][target] == 1;
  10.     // 选择当前元素
  11.     bool select = dfs(nums, index + 1, target - nums[index], map);
  12.     // 不选择当前元素
  13.     bool unSelect = dfs(nums, index + 1, target, map);
  14.     // 存储结果，并返回
  15.     map[index][target] = select || unSelect ? 1 : 0;
  16.     return select || unSelect;
  17. }
  18.  
  19. bool canPartition(std::vector<int>& nums) {
  20.     // 计算数组中所有元素的和
  21.     int sum = 0;
  22.     for (int num : nums) sum += num;
  23.     // 如果sum是奇数，说明数组不可能分成完全相等的两份
  24.     if (sum % 2 != 0) return false;
  25.     // sum除以2
  26.     int target = sum / 2;
  27.     std::vector<std::vector<int>> map(nums.size(), std::vector<int>(target + 1, -1));
  28.     return dfs(nums, 0, target, map);
  29. }

4. Idée de solution 3

Solution d'opération de bits

Les opérations sur les bits peuvent être utilisées ici, mais la clé réside dans certaines restrictions de la question, comme un tableau non vide d'entiers positifs, les éléments de chaque tableau ne dépasseront pas 100, la taille du tableau ne dépassera pas 200, etc. .
Le principe est très simple. Il suffit de demander un tableau bits[somme+1] de taille somme+1. Les nombres dans le tableau ne peuvent être que 0 et 1. On peut l'imaginer comme un bit binaire très long, car. int et Le type long est trop court, nous utilisons ici un tableau. Ensuite, chaque fois qu'un élément du tableau est parcouru, tel que m, le bit binaire est décalé vers la gauche de m bits, puis soumis à un OU avec le bit binaire d'origine. Enfin, déterminez si bits[sum/2] vaut 1 et renvoyez true s'il vaut 1.La description textuelle n’est pas très simple. Prenons l’exemple 1 comme exemple pour dessiner une image.

Enfin, vous trouverez une règle, c'est-à-dire que tant que le résultat final de l'opération est 1, il peut être combiné en utilisant les éléments du tableau. Tant qu'il est 0, il ne peut pas être combiné en utilisant les éléments du tableau. processus ci-dessus, le code est facile à écrire. Parce que nous avons seulement besoin de déterminer si la valeur moyenne du bit binaire est 1, nous avons seulement besoin de calculer le bit bas, et le bit haut n'a pas besoin d'être calculé du tout, car il est déplacé vers la gauche et le bit haut bit n'aura aucun impact sur la valeur moyenne, nous pouvons donc le faire ici. Un peu d'optimisation, et enfin regardons le code.

  1. #include <vector>
  2.  
  3. bool canPartition(std::vector<int>& nums) {
  4.     // 计算数组中所有数字的和
  5.     int sum = 0;
  6.     for (int n : nums) {
  7.         sum += n;
  8.     }
  9.     // 如果sum是奇数，直接返回false
  10.     if ((sum & 1) == 1) {
  11.         return false;
  12.     }
  13.     int len = sum / 2;
  14.     // 这里bits的长度是len+1，因为我们只需要计算低位就行了，没必要计算所有的
  15.     std::vector<char> bits(len + 1, 0);
  16.     bits[0] = 1;
  17.     for (int num : nums) {
  18.         for (int j = len - num; j >= 0; j--) {
  19.             bits[j + num] |= bits[j];
  20.         }
  21.         // 判断中位数如果是1，说明可以分成两种相等的子集，直接返回true，不需要再计算了
  22.         if ((bits[len] & 1) != 0) {
  23.             return true;
  24.         }
  25.     }
  26.     return false;
  27. }

Profil personnel

Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.

mes coordonnées

Mail