CMP.8:5.1 - Round profits to construct a shorter discrete computation

Choose a subset of items within capacity W to maximize total profit. After removing items individually too heavy, suppose there are n items with positive integer weights and nonnegative integer profits p_i. If no positive profit remains, the empty subset is optimal. Otherwise let P=max p_i; at least that one item is feasible, so P≤OPT.

For 0<ε<1, set K=ε*P/n and scaled profits q_i=floor(p_i/K). Keep weights and capacity unchanged. Construct a dynamic program D(j,q) returning the minimum weight of a subset of the first j items with total scaled profit q:

D(0,0) = 0; D(0,q) = infinity for q > 0
D(j,q) = min(D(j-1,q), w_j + D(j-1,q-q_j))

An out-of-range index is infeasible. Retain enough choices to recover a subset, and select the largest q with D(n,q)≤W. Including zero, there are at most n*floor(n/ε)+1 scaled-profit positions. The straightforward table therefore takes O(n³/ε) arithmetic operations; weight arithmetic and witness storage have their own costs. Compute the rounding reliably when ε is supplied as a finite rational value.

Let A be the returned subset and O an original optimum. Because A maximizes the scaled profit among the same feasible subsets,

p(A) ≥ K*q(A) ≥ K*q(O) > p(O)-n*K ≥ (1-ε)*OPT.

The strict middle inequality follows from losing less than K on each of at most n selected items. Thus the returned object remains feasible and its loss is controlled, without knowing OPT in advance.

For A=(weight 5, profit 12), B=(3,7), C=(2,6), capacity 5 and ε=1/2, K=2 and scaled profits are 6,3,3. A and {B,C} tie under the scaled objective; a rule retaining A returns profit 12 although the optimum is 13. The approximation claim permits this. With ε=1/4, K=1 and the scaled objective distinguishes profit 13 from 12, returning {B,C}.

If the requested result changes to every optimal subset, the former error guarantee is insufficient. K=1 restores the original integer objective and lets this table obtain the optimal value, but can restore the large table the approximation was designed to avoid. Enumerating every optimum also requires reconstruction of every feasible subset attaining that value, including alternatives discarded by the minimum-weight entry. For example, with capacity 2 and two items of weights 1 and 2, each with profit 5, either singleton is optimal, although the minimum-weight entry retains only the first. The number of optimal subsets, and hence enumeration output, can be exponential. CMP.4 offers search with bounds; the cost and output requirement decide the choice.