C++ 集合划分是NP完全问题

集合划分是一个NP完全问题，其任务是确定是否可以将给定的一组正整数分成两个和相等的子集。NP完全意味着没有已知的多项式时间算法可以解决所有情况，而验证一个可能的解可以在多项式时间内完成。许多其他NP完全问题可以归约到集合划分问题，表明它的计算复杂性以及在理解更广泛的NP完全问题类中的重要性。由于其复杂性，解决集合划分问题的大规模实例可能需要显著的时间投资，难以有效地找到最佳解。

使用的方法

暴力法
回溯法

暴力法

暴力法是一种直接且直接的算法方法，通过评估每一个可能的解决方案并选择正确的解决方案来解决问题。它包括有效列举所有可能的解决方案，并实际检查每一个解决方案是否满足问题的要求。虽然暴力法在逻辑上简单和易于实现，但对于解空间较大的问题而言，它可能是计算上低效和不切实际的。

尽管暴力法简单，但对于具有小输入大小或解空间相对较小的问题，它是一种可行的方法。它通常用于简单的问题，作为验证正确性的模式，或者作为应用更复杂算法之前的起点。

步骤

计算集合中所有元素的总和，并检查是否可被 2 整除。如果不行，返回 “No solution”。
初始化两个空集合 subset1 和 subset2。
使用起始集合 S、subset1、subset2 和目标总和（totalSum / 2）调用递归函数 partitionHelper。
在 partitionHelper 函数中：
检查 subset1 中的元素总和是否等于目标总和。如果是，则打印 subset1 和 subset2，并返回。如果集合 S 为空，则返回。选择集合 S 中的元素 x 并将其从 S 中删除。
尝试将 x 添加到 subset1，并使用更新后的 S、subset1、subset2 和目标总和递归调用 partitionHelper。
如果上述调用未找到有效的划分，则从 subset1 中移除 x 并尝试将 x 添加到 subset2。
使用更新后的 S、subset1、subset2 和目标总和递归调用 partitionHelper。
如果在递归过程中找不到有效的划分，则打印 “No solution”。

示例

#include <iostream>
#include <vector>

bool partitionHelper(std::vector<int> S, std::vector<int>& 
subset1, std::vector<int>& subset2, int targetSum) {
   if (targetSum == 0) {
      std::cout << "Subset 1: ";
      for (int num : subset1) {
         std::cout << num << " ";
      }
      std::cout << "\nSubset 2: ";
      for (int num : subset2) {
         std::cout << num << " ";
      }
      return true;
   }

   if (S.empty()) {
      return false;
   }

   int x = S.back();
   S.pop_back();

   subset1.push_back(x);
   if (partitionHelper(S, subset1, subset2, targetSum - x)) {
      return true;
   }
   subset1.pop_back();

   subset2.push_back(x);
   if (partitionHelper(S, subset1, subset2, targetSum - x)) {
      return true;
   }
   subset2.pop_back();

   return false;
}

void partition(const std::vector<int>& S) {
   int totalSum = 0;
   for (int num : S) {
      totalSum += num;
   }
   if (totalSum % 2 != 0) {
      std::cout << "No solution.\n";
      return;
   }

   std::vector<int> subset1, subset2;
   int targetSum = totalSum / 2;

   if (!partitionHelper(S, subset1, subset2, targetSum)) {
      std::cout << "No solution.\n";
   }
}

int main() {
   std::vector<int> set = {1, 2, 3, 4, 5, 6};
   partition(set);
   return 0;
}

输出

No solution.

回溯算法

回溯是一种用于有意地寻找组合问题答案的整体算法方法。它是一种试验搜索的方式，算法探索各种可能性，逐步构建可行解，并在意识到当前路径无法导致有效解时进行回溯。

回溯算法可以被视为探索一棵树，其中每个节点表示在特定步骤上做出的选择，而分支则表示该选择的潜在结果。算法以深度优先的方式遍历树，逐个探索每条路径，直到找到有效解或耗尽所有可能性。

步骤

开始时有两个空集合SetA和SetB，分别表示正在形成的两个子集。
递归地探索从给定集合中选择的所有可能组合，用于包含在SetA和SetB中。
在每个步骤中，要么将一个元素添加到SetA并对剩余元素进行递归，要么将其添加到SetB并进行递归。
在递归过程中，监视SetA和SetB的元素数量。
如果SetA的数量在任何时刻达到SetB的数量，则返回“有效”，否则返回“错误”。

示例

#include <iostream>
#include <vector>

bool isValidSubset(const std::vector<int>& inputSet, int index, int 
setSizeA, int setSizeB) {
   if (index == inputSet.size()) {
      return (setSizeA == setSizeB);
   }

   bool isValid = isValidSubset(inputSet, index + 1, setSizeA + 1, setSizeB);
   isValid |= isValidSubset(inputSet, index + 1, setSizeA, setSizeB + 1);

   return isValid;
}

int main() {
   std::vector<int> inputSet = {1000, 2000, 3000, 4000, 5000};
   bool isValid = isValidSubset(inputSet, 0, 0, 0);
   std::cout << (isValid ? "Valid" : "Misleading") << std::endl;
   return 0;
}

输出

Misleading

结论

本文研究了集合分割问题的NP完全性，包括决定给定一组正整数是否可以被划分为两个子集合使得它们的和相等。NP完全性意味着对于所有情况，没有已知的多项式时间算法可以解决该问题，并且验证一个可能的解决方案可以在多项式时间内完成。本文探讨了三种解决该问题的方法：穷举法、回溯法和动态规划。由于其复杂性，解决大规模的集合分割问题可能需要大量的时间和努力，使得寻找一个最优解决方案变得困难。了解集合分割问题的复杂性很重要，因为它与其他NP完全问题有关，并为计算上复杂问题提供了更广泛的教训。