0-1 knapsack problem ($\max \{v^{\mathsf{T}}x:w^{\mathsf{T}}x\le B,x\in \{0,1{\}}^n\}$)

This binary integer program selects each item at most once. Exact optimization is NP-hard; the fractional knapsack problem gives an upper bound and supports a half-approximation algorithm for knapsack.

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$.