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.

Assign each item to neither bag or exactly one of two bags, respecting both capacities and maximizing total value. With nonnegative integer capacities $W_1,W_2$, a dynamic programming state indexed by the item prefix and both capacities gives $O(n(W_1+1)(W_2+1))$ time complexity. Every transition uses the preceding item layer to prevent reuse of an item.

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