集合划分是NP完全的

将包裹集合问题（Set Parcel）翻译成中文，这是一个NP完全问题，任务是确定给定的一组正整数是否可以分成两个子集，使得它们的总和相等。NP完全意味着目前没有已知的多项式时间算法能够解决所有情况，而验证一个可能的解决方案应该可以在多项式时间内完成。许多其他的NP完全问题可以归约到Set Parcel问题，表明它的计算复杂性以及在理解更广泛的NP完全问题类别中的重要性。由于其复杂性，解决Set Parcel问题的大规模案例可能需要巨大的时间投入，这使得有效地找到一个最佳解决方案变得困难。

Methods Used

• Brute Force

• 回溯算法

Brute Force

暴力破解是一种直接而无辜的算法方法，用于通过评估每一种可能的排列并选择正确的排列来解决问题。它包括高效地列举每一种可能的排列，并实际检查每一种排列是否满足问题的要求。虽然暴力破解方法在思路上简单易懂且易于实施，但对于具有庞大排列空间的问题来说，它可能计算效率低下且不切实际

Regardless of its straightforwardness, savage power can be a substantial methodology for issues with little info sizes or when the arrangement space is generally little and reasonable. It is regularly utilized for straightforward issues, as a pattern to confirm rightness, or as a beginning stage prior to applying more modern calculations.

Algorithm

• 计算集合中所有组件的完整性，并检查它们是否可以被2整除。如果不能，返回"无解"。

• Initialize two purge sets, subset1 and subset2.

• 调用递归工作分割助手 partitionHelper，使用起始集合 S，子集 1，子集 2 和目标整体（totalSum / 2）

在partitionHelper函数中：

• Check on the off chance that the entirety of components in subset 1 is equal to the target whole. On the off chance that so, print subsets 1 and 2, and return. 如果集合S是清除的，则返回 Choose component x from S and expel it from S.

• Try including x in subset1 and calling partitionHelper recursively with the upgraded S, subset1, subset2, and the target sum.

如果叫牌没有发现一个大的包裹，从子集1中排除x并尝试将x包含在子集2中

• 使用重组后的S、子集1、子集2和目标总和递归调用partitionHelper函数

• If no substantial segment is found amid the recursion, print "No arrangement."

Example

#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.

Backtracking

Backtracking is an overall algorithmic method used to look for answers for combinatorial issues deliberately. It is a type of experimentation search where the calculation investigates various conceivable outcomes, steadily constructing a possible arrangement and backtracks when it understands that the ebb and flow way can't prompt a substantial arrangement.

回溯系统可以被想象成一个调查树，其中每个节点代表在特定步骤上做出的决策，而分支代表该决策的潜在结果。算法按照深度优先的方式遍历树，依次探索每条路径，直到找到一个有效解决方案或者耗尽所有可能性。

Algorithm

• Begin with two void sets, SetA and SetB, to address the two subsets being shaped.

• 递归地调查来自给定集合的组件的所有潜在混合，以便记住SetA和SetB中的内容

• 在每一步中，将一个组件添加到SetA并对多余的组件进行递归，或将其添加到SetB并进行递归

• 在递归过程中监控SetA和SetB的数量

• If anytime, the amount of SetA rises to the amount of SetB, bring Valid back; in any case, get back Misleading.

Example

#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完备问题相关，为我们揭示了计算复杂问题的更广泛教训

以上是集合划分是NP完全的的详细内容。更多信息请关注PHP中文网其他相关文章！