Set partitioning is NP-complete

Translate the Set Parcel problem into Chinese. This is an NP-complete problem. The task is to determine whether a given set of positive integers can be divided into two subsets such that they The sum of is equal. NP-complete means that no currently known polynomial-time algorithm can solve all cases, and verifying a possible solution should be done in polynomial time. Many other NP-complete problems can be reduced to the Set Parcel problem, demonstrating its computational complexity and importance in understanding the broader class of NP-complete problems. Due to its complexity, solving large-scale cases of the Set Parcel problem can require a huge time investment, which makes it difficult to efficiently find an optimal solution.

Methods Used

• Brute Force

• Backtracking algorithm

Brute Force

Brute force is a straightforward and innocent algorithmic approach to solving a problem by evaluating every possible permutation and choosing the correct one. It involves efficiently enumerating every possible permutation and actually checking whether each permutation meets the requirements of the problem. Although the brute-force approach is conceptually simple and easy to implement, it can be computationally inefficient and impractical for problems with large permutation spaces.

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

• Calculate the completeness of all components in the set and check whether they are divisible by 2. If not, return "No solution".

• Initialize two purge sets, subset1 and subset2.

• Call the recursive work partitioning assistant partitionHelper, using the starting set S, subset 1, subset 2 and the target whole (totalSum / 2)

In the partitionHelper function:

• 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. If the set S is cleared, return 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.

If the bid does not find a large parcel, exclude x from subset 1 and try to include x in subset 2

• Recursively call the partitionHelper function using the reorganized S, subset 1, subset 2 and target sum

• 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;
}

Output

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.

A backtracking system can be imagined as an investigation tree, where each node represents a decision made at a specific step, and the branches represent potential outcomes of that decision. The algorithm traverses the tree in a depth-first fashion, exploring each path in turn until it finds a valid solution or exhausts all possibilities.

Algorithm

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

• Recursively investigate all potential mixes of components from a given set, in order to remember what is in SetA and SetB

• At each step, add a component to SetA and recurse on the extra components, or add it to SetB and recurse

• Monitor the number of SetA and SetB during the recursive process

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

The above is the detailed content of Set partitioning is NP-complete. For more information, please follow other related articles on the PHP Chinese website!