Half-approximation algorithm for knapsack ($\mathrm{ALG}\ge \frac{1}{2}\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$.