Fractional knapsack problem
= Fractional knapsack problem
{title2=$0\leq x_i\leq1$}
This <linear programming> relaxation allows a fraction of each item. With positive weights, sort decreasing profit-to-weight ratios and fill capacity in that order, using at most one fractional item. An exchange argument proves optimality. Negative-profit items are omitted and positive-profit zero-weight items are included for free.