数据结构
网络
关系数据库管理系统 (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 次浏览
