★ 合取范式的可满足性问题CNF-SAT
如果一个布尔合取范式的每个乘积项最多是k个因子的析取式,就称之为k元合取范式,简记为k-CNF.一个k-SAT问题是判定一个k-CNF是否可满足.特别地,当k=3 时,3-SAT问题在NP完全问题树中具有重要地位.
给定k个布尔变量1 x ,..., k x 的m个布尔表达式1 A ,..., m A ,每个布尔表达式i A 都有一个权值wi,求各布尔变量i x (1≤i≤k)的0,1赋值,使取值1 的布尔表达式权值之和达到最大.
对于给定的带权3-CNF,设计一个蒙特卡罗算法,使其权值之和尽可能大.
接下来的m行中,每行有5 个整数wijk0,表示相应表达式的权值为w,表达式含的变量下标分别为ijk,行末以0 结尾.下标为负数时,表示相应的变量为取反变量.