Pro.ID2087 TitleAL093 3SAT问题 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=2087 AC0 Submit0 Ratio- 时间&空间限制描述SAT的一个实例是k个布尔变量 x1 ，…， xk 的m个布尔表达式 A1 ，…， Am 。若存在各布尔变量 xi ( 1 <= i <= k )的0，1 赋值，使每个布尔表达式 Ai ( 1 <= i <= m ) 都取值1，则称布尔表达式 A1A2 … Am 是可满足的。 ★ 合取范式的可满足性问题CNF-SAT 如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(Conjunctive Normal Form)。这里的因子是变量x或~x。例如 ( x1 + x2) ( x2 + x3 ) ( ~x1 + ~x2 + x3 ) 就是一个合取范式，而 x1 x2 + x3 就不是合取范式。 ★ k-SAT 如果一个布尔合取范式的每个乘积项最多是k个因子的析取式，就称之为k元合取范式，简记为k-CNF。一个k-SAT问题是判定一个k-CNF是否可满足。特别地，当k=3 时，3-SAT 问题在NP完全问题树中具有重要地位。 ★ MAX-SAT 给定k个布尔变量 x1 ，…， xk 的m个布尔表达式 A1 ，…， Am ，求各布尔变量 xi ( 1 <= i <= k ) 的0，1 赋值，使尽可能多的布尔表达式 Ai 取值1。 ★ Weighted-MAX-SAT 给定k个布尔变量 x1 ，…， xk 的m个布尔表达式 A1 ，…， Am ，每个布尔表达式 Ai 都有一个权值wi，求各布尔变量 xi ( 1 <= i <= k )的0，1赋值，使取值1 的布尔表达式权值之和达到最大。 对于给定的带权3-CNF，设计一个蒙特卡罗算法，使其权值之和尽可能大。 输入输入第一行有两个正整数k和m，分别表示变量数和布尔表达式数。接下来的m行中，每行有5个整数w,i,j,k,0，表示相应表达式的权值为w，表达式含的变量下标分别为i,j,k，行末以0 结尾。下标为负数时，表示相应的变量为取反变量。 输出Description SAT的一个实例是k个布尔变量 x1 ，…， xk 的m个布尔表达式 A1 ，…， Am 。若存在各布尔变量 xi ( 1 <= i <= k )的0，1 赋值，使每个布尔表达式 Ai ( 1 <= i <= m ) 都取值1，则称布尔表达式 A1A2 … Am 是可满足的。 ★ 合取范式的可满足性问题CNF-SAT 如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(Conjunctive Normal Form)。这里的因子是变量x或~x。例如 ( x1 + x2) ( x2 + x3 ) ( ~x1 + ~x2 + x3 ) 就是一个合取范式，而 x1 x2 + x3 就不是合取范式。 ★ k-SAT 如果一个布尔合取范式的每个乘积项最多是k个因子的析取式，就称之为k元合取范式，简记为k-CNF。一个k-SAT问题是判定一个k-CNF是否可满足。特别地，当k=3 时，3-SAT 问题在NP完全问题树中具有重要地位。 ★ MAX-SAT 给定k个布尔变量 x1 ，…， xk 的m个布尔表达式 A1 ，…， Am ，求各布尔变量 xi ( 1 <= i <= k ) 的0，1 赋值，使尽可能多的布尔表达式 Ai 取值1。 ★ Weighted-MAX-SAT 给定k个布尔变量 x1 ，…， xk 的m个布尔表达式 A1 ，…， Am ，每个布尔表达式 Ai 都有一个权值wi，求各布尔变量 xi ( 1 <= i <= k )的0，1赋值，使取值1 的布尔表达式权值之和达到最大。 对于给定的带权3-CNF，设计一个蒙特卡罗算法，使其权值之和尽可能大。 Input 输入第一行有两个正整数k和m，分别表示变量数和布尔表达式数。接下来的m行中，每行有5个整数w,i,j,k,0，表示相应表达式的权值为w，表达式含的变量下标分别为i,j,k，行末以0 结尾。下标为负数时，表示相应的变量为取反变量。 Output 输出最大权值 Sample Input 5 3 9 3 1 4 0 9 1 -5 3 0 8 2 -5 1 0 Sample Output 26 样例输入5 3 9 3 1 4 0 9 1 -5 3 0 8 2 -5 1 0 样例输出26 提示作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2024-9-21 13:50 , Processed in 0.016763 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
