Half-approximation algorithm for knapsack
= Half-approximation algorithm for knapsack
{title2=$\mathrm{ALG}\geq\tfrac12\mathrm{OPT}$}
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$.