Let y=<y1, ... yn> be any truth assignment for an instance I of Max Weighted Sat (i.e. each clause C has a positive weight w(C)) on variables x1,...,xn. Let z=<z1, ... zn> b the complement of y, that is zi is true if and only if yi is false.
Compute the weight of the clauses satisfied by y and of those satisfied by z. Return the assignment that has largest weight.
Prove that the above algorithm achieves a 1/2-approximation