主观题：MAX 3-SAT problem

Given a 3-SAT formula with $$k$$ clauses, in which each clause has three variables, the **MAX 3-SAT** problem is to find a truth assignment that satisfies as many clauses as possible. A simple randomized algorithm is to flip a coin, and to set each variable true with probability 1/2, independently for each variable. 

Prove that the expected number of clauses satisfied is $$7k/8$$.  Hence if we repeatedly generate random truth assignments until one of them satisfies $$\ge 7k/8$$ clauses, then this algorithm is a 8/7-approximation algorithm.





答案：