資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學子集相等性是NP完全問題
子集和問題，也稱為“子集總和”問題，是一個經典的NP完全計算問題。給定一組數字和一個目標值，任務是確定是否存在一個數字子集，其總和等於目標值。該問題的NP完全性源於其能夠透過多項式時間歸約來表達許多其他NP完全問題的能力。儘管其定義簡單，但沒有已知的有效演算法能夠解決所有例項的“子集和”問題，這使其成為理論計算機科學和最佳化領域的重要研究課題，並在密碼學、資源分配和動態規劃等各個領域具有實際應用。
使用的方法
從子集和問題歸約
從3SAT歸約
從子集和問題歸約
證明“子集相等性”是NP完全問題的一種方法是從著名的NP完全問題“子集和”問題進行歸約。
演算法
給定一個“子集和”問題的例項，即一組整數S和一個目標值T。
建立一個“子集相等性”問題的另一個例項，使用相同的集合S和目標值2T。
如果在“子集和”問題中存在一個總和為T的S的子集，那麼在“子集相等性”問題中將存在一個總和為2T的子集，方法是將相同的子集自身相加。
如果在“子集和”問題中不存在一個總和為T的S的子集，那麼在“子集相等性”問題中也不存在一個總和為2T的子集，因為任何總和小於2T的子集與其自身相加都不能超過2T。
這種歸約表明，解決“子集相等性”與解決“子集和”問題一樣困難，因此它是NP完全的。
示例
#include <iostream>
#include <vector>
using namespace std;
bool isSubsetSum(vector<int>& set, int n, int sum) {
if (sum == 0) return true;
if (n == 0) return false;
if (set[n - 1] > sum) return isSubsetSum(set, n - 1, sum);
return isSubsetSum(set, n - 1, sum) || isSubsetSum(set, n - 1, sum - set[n - 1]);
}
bool isSubsetAggregateReduction(vector<int>& set, int n, int sum) {
return !isSubsetSum(set, n, sum) && !isSubsetSum(set, n, 2 * sum);
}
int main() {
vector<int> set = {3, 34, 4, 12, 5, 2};
int sum = 18;
if (isSubsetAggregateReduction(set, set.size(), sum)) {
cout << "No subset exists in Subset Aggregate issue that sums to " << sum << " and no subset exists that sums to " << 2 * sum << " by adding the same subset with itself." << endl;
} else {
cout << "There exists a subset in Subset Aggregate issue that sums to " << sum << " or a subset in Subset Equity issue that sums to " << 2 * sum << " by adding the same subset with itself." << endl;
}
return 0;
}
輸出
There exists a subset in Subset Aggregate issue that sums to 18 or a subset in Subset Equity issue that sums to 36 by adding the same subset with itself.
從3SAT歸約
另一種方法是透過從另一個已知的NP完全問題（例如3SAT問題）直接歸約來證明“子集相等性”是NP完全的。
演算法
給定一個3SAT問題的例項，它包含一個合取正規化中的布林公式，每個子句都有三個文字。
建立一個“子集相等性”問題的另一個例項，其中有一組整數和一個目標值，如下所示：
如果3SAT公式是可滿足的，則在“子集相等性”問題中存在一個總和等於目標值的子集，方法是為每個滿足的子句選擇一個變數。
如果3SAT公式不可滿足，則在“子集相等性”問題中不存在一個總和等於目標值的子集，因為任何有效的子集都必須至少包含一個值為2的整數，對應於一個滿足的子句。
由於3SAT問題已知是NP完全的，因此這種歸約證明了“子集相等性”的NP完全性。
a. 對於3SAT公式中的每個變數，建立一個值為1的數字。
b. 對於3SAT公式中的每個子句，建立一個值為2的數字。
c. 將目標值設定為3SAT公式中變數的總數加上子句的總數。
示例
#include <iostream>
#include <vector>
using namespace std;
bool ThreeSAT_Satisfiable(const vector<vector<int>>& clauses) {
return false;
}
class SubsetUniformity {
private:
vector<int> numbers;
int targetValue;
public:
SubsetUniformity(const vector<int>& vars, const vector<int>& clauses) {
for (int v : vars) {
numbers.push_back(1);
}
for (int c : clauses) {
numbers.push_back(2);
}
targetValue = vars.size() + clauses.size();
}
bool isSubsetSumPossible(int idx, int sum) {
if (sum == targetValue) {
return true;
}
if (idx >= numbers.size() || sum > targetValue) {
return false;
}
return isSubsetSumPossible(idx + 1, sum) || isSubsetSumPossible(idx + 1, sum + numbers[idx]);
}
bool hasSolution() {
return isSubsetSumPossible(0, 0);
}
};
int main() {
vector<vector<int>> clauses = {
{1, 2, -3},
{-1, -2, 3},
{-1, 2, 3}
};
bool isSatisfiable = ThreeSAT_Satisfiable(clauses);
SubsetUniformity su(clauses[0], clauses[1]);
cout << "3SAT Formula is " << (isSatisfiable ? "satisfiable." : "not satisfiable.") << endl;
cout << "Subset Uniformity has " << (su.hasSolution() ? "a" : "no") << " solution." << endl;
return 0;
}
輸出
3SAT Formula is not satisfiable. Subset Uniformity has a solution.
結論
這兩種方法都表明“子集相等性”（或“子集和”問題）是NP完全的，因此找到一個有效的演算法來解決所有例項不太可能。研究人員經常使用動態規劃或其他近似方法來有效地解決該問題的實際例項。
143 次瀏覽
