資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究集合劃分問題是NP完全問題
集合劃分是一個NP完全問題，其中任務是確定給定的一組正整數是否可以劃分為兩個和相等的子集。NP完全性意味著對於所有例項，都沒有已知的可以解決它的多項式時間演算法，並且可以在多項式時間內驗證一個可能的解決方案。許多其他NP完全問題可以歸約為集合劃分，這證明了它的計算複雜性和它在理解更廣泛的NP完全問題類別中的重要性。由於它的複雜性，解決集合劃分問題的大型例項可能需要大量的時間和精力，這使得有效地找到最優解變得具有挑戰性。
使用的方法
暴力法
回溯法
暴力法
暴力法是一種直接且簡單的演算法方法，用於透過評估所有可能的解決方案並選擇正確的解決方案來解決問題。它包括系統地列出所有可能的解決方案，並實際檢查每一個解決方案以檢視它是否滿足問題的要求。雖然暴力法在概念上很簡單且易於實現，但對於具有大型解決方案空間的問題，它在計算上可能效率低下且不可行。
儘管簡單，但對於輸入大小較小或解決方案空間相對較小且可行的問題，暴力法可能是一種可行的策略。它通常用於簡單的問題，作為驗證正確性的手段，或作為在應用更高階的演算法之前的起點。
演算法
計算集合中所有元素的總和，並檢查它是否可以被2整除。如果不是，則返回“無解”。
初始化兩個空集，subset1和subset2。
呼叫遞迴函式partitionHelper，傳入起始集合S、subset 1、subset 2和目標總和（totalSum / 2）。
在partitionHelper函式中
檢查subset 1中元素的總和是否等於目標總和。如果是，則列印subset 1和subset 2，並返回。如果集合S為空，則返回。從S中選擇元素x並將其從S中移除。
嘗試將x包含在subset1中，並使用更新後的S、subset1、subset2和目標總和遞迴呼叫partitionHelper。
如果上述呼叫未找到有效的劃分，則從subset 1中移除x，並嘗試將x包含在subset 2中。
使用更新後的S、subset 1、subset 2和目標總和遞迴呼叫partitionHelper。
如果在遞迴過程中未找到有效的劃分，則列印“無解”。
示例
#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的總和，則返回True；否則，返回False。
示例
#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完全問題相關，揭示了計算複雜問題的更廣泛的教訓。
156 次檢視
