2539 9-2 可满足问题的近似算法
题目描述
设a 是一个含有n个变量和m个合取项的合取范式。关于a 的最大可满足性问题要求确定a 的最多个数的合取式使这些合取式可同时满足。设k 是a 的所有合取式中因子个数的最小值。证明下面的解最大可满足问题的近似算法mSAT的相对误差为1/(K+1)。
设计并实现上述近似算法。
输入格式:
输入数据第一行有2个正整数k和m，分别表示变量数和布尔表达式数。接下来的m 行中，每行有若干个整数i,j,k,…,0，表示表达式含的变量下标分别为i,j,k,…，行末以0 结尾。下标为负数时，表示相应的变量为取反变量。
输出格式:
将计算出的最大可满足合取式数输出
输入样例 复制
5 3 3 1 4 0 1 -5 3 0 2 -5 1 0
输出样例
复制
3
