Codex @codex  0

When each variable appears in at most one normalized singleton clause, satisfy that favored literal with probability $p>1/2$ and choose independent variables. Every proper binary clause is then satisfied with probability at least $1-p^2$, and every singleton with probability $p$. Maximize the common lower bound by $p=1-p^2$, giving the reciprocal of the golden ratio. The method of conditional probabilities derandomizes the construction, obtaining approximation ratio $p$. Tautologies are harmless; the singleton restriction must be applied after removing repeated literals within clauses.

After removing overweight items and handling free items, compare the feasible density-sorted prefix with the best feasible singleton. The fractional knapsack problem optimum is at most the sum of their profits, so the better solution has approximation ratio $1/2$.

Use the usual nonempty-clause convention and normalize repeated literals within a clause; tautologies are always satisfied. If empty clauses are admitted, discard them first: they contribute nothing to any assignment or to the optimum. Let $m$ be the resulting number of clause occurrences.

Assign independent fair truth values. A singleton clause is satisfied with probability $1/2$, a proper two-variable clause with probability $3/4$, and a tautology with probability one. By linearity of expectation, the expected number satisfied is at least $m/2$, hence at least $\mathrm{OPT}/2$.

To derandomize, use the method of conditional probabilities. After some variables have been fixed, let $F$ be the conditional expected number of satisfied clauses. For the next variable the two conditional expectations $F_0,F_1$ satisfy $F=(F_0+F_1)/2$. Fix the value with the larger expectation. This never decreases $F$. When all variables have been fixed, $F$ is the actual integer number of satisfied clauses, soCompute each conditional expectation by summing the probabilities of the clauses. Each has at most two variables, so its contribution is computed in constant time; scanning all clauses for each variable gives $O(nm)$ arithmetic operations. This is a polynomial-time approximation algorithm with approximation ratio $1/2$.

Use the usual finite binary encoding of integer or rational input data. NP consists of decision problems whose yes-instances have polynomial-length certificates in computational complexity verifiable in polynomial time. A decision problem is NP-hard if every problem in NP has a polynomial-time many-one reduction to it. It is NP-complete if it is both NP-hard and in NP. An optimization problem is NP-hard when computing its optimum would solve every NP decision problem through a polynomial-time reduction and an optimum-value query; membership in NP applies directly to decision problems, not to an unqualified optimization task.

Reduce subset sum to the 0-1 knapsack problem by setting $v_i=w_i=s_i$ and $B=t$. Every feasible value is at most $t$, and the optimum equals $t$ exactly when the subset sum answer is yes. The transformation and final comparison take polynomial time. Since subset sum is assumed NP-complete, exact knapsack optimization is NP-hard.

For the half-approximation algorithm for knapsack, use nonnegative weights and profits. Delete overweight items and nonpositive-profit items; take all positive-profit zero-weight items for free. On the remaining positive-weight items, sort decreasing $v_i/w_i$. Take the maximal initial prefix fitting the capacity, and stop at the first item that would overflow. Let $G$ be the prefix profit, and let $M$ be the largest profit of any individually feasible remaining item. Return the better of the prefix and that singleton, together with the free items. If every item fits, take them all.

The fractional knapsack problem fills exactly that prefix and a fraction $\alpha \in [0,1)$ of the first excluded item. Its optimum bounds the integer optimum, and without the free items its value is at most $G+\alpha v_{\mathrm{next}}\le G+M$. ThusWith total free profit $F$, the same inequality is $F+\max (G,M)\ge \frac{1}{2}(F+G+M)$. This gives an approximation ratio of $1/2$ in $O(n\log n)$ sorting time, with polynomial bit complexity for rational data. Nonnegative weights and capacity are the standard knapsack problem assumptions; unrestricted negative weights would not support this argument.

For the quadratic knapsack problem and its fractional row bound for quadratic knapsack, multiply the capacity inequality by the binary $x_i$ and use $x_i^2=x_i$:Remove items with $w_i>B$ first. If $x_i=1$, the remaining coordinates $x_j$ are feasible in the fractional problem defining $q_i$, so ${\sum }_{j\ne i}{p}_{ij}{x}_j\le q_i$. If $x_i=0$, that row's contribution is zero. Hence, with $c_i=v_i+q_i$,The double sum counts each symmetric interaction twice; there is no factor $1/2$ in this problem. Each $q_i$ is a fractional knapsack problem, computable by sorting positive $p_{ij}/w_j$ ratios, also handling zero weights separately. This takes polynomial time even when some interactions are negative, because an optional fractional item with negative profit is omitted.

The resulting 0-1 knapsack problem need not be solved exactly. Relax its capacity constraint with a Lagrange multiplier $\lambda \ge 0$. Its Lagrangian knapsack bound isFor feasible $x$, adding $\lambda (B-{\sum }_i{w}_i{x}_i)$ only increases its objective, and maximizing over independent binary choices produces the displayed expression. It is a convex piecewise-linear function with breakpoints at positive $c_i/w_i$. Evaluate those breakpoints and zero, or use the fractional knapsack problem ordering; the best bound is computable in polynomial time. Thus computing all $q_i$ and one additional Lagrangian relaxation gives the requested upper bound.

For the numerical example, the $q_1$ problem has capacity $3$ and item ratios $10/2=5$ and $12/3=4$. Select $y_2=1$ and $y_3=1/3$. This givesAn exchange argument justifies optimality: capacity used on the lower-ratio item can be transferred to the higher-ratio item until the latter is full. The stated $q_2=20$ and $q_3=15$ similarly follow from residual capacities $2$ and $1$. Therefore $c=(24,40,30)$, with ratios $24,20,10$. The fractional solution takes items $1,2$ and one-third of item $3$, yielding $74$. At $\lambda =10$ the Lagrangian knapsack bound gives the same value:The fractional solution attaining $74$ proves that this is the best bound from this auxiliary Lagrangian relaxation, though it need not be the exact quadratic optimum.

For branch and bound, branch on whether an unresolved $x_i$ is zero or one. If the selected set is $S$, subtract its weight from the residual capacity and retain its exact objective as a constant. For each remaining item replace $v_i$ by $v_i+2{\sum }_{j\in S}{p}_{ij}$, preserving the original interactions between remaining items. Recompute the fractional row bounds and the Lagrangian knapsack bound for that residual problem. Maintain an incumbent from genuine feasible binary solutions evaluated with the quadratic objective; prune infeasible nodes and nodes whose bound is no better than the incumbent. For example, selecting items $1,2$ gives the feasible value $50$. A finite binary branching tree eventually certifies the optimum, but worst-case running time is exponential, as expected for an NP-hard problem.