The knapsack problem selects items of prescribed weights and profits under a total-weight capacity. The 0-1 knapsack problem permits each item at most once; bounded and unbounded multiplicity variants use different integer restrictions. Nonnegative weights and capacity are assumed here.
The quadratic knapsack problem includes pairwise interactions between selected items. For symmetric , a sum over all ordered pairs counts each unordered interaction twice; an alternative convention sums only over . The objective convention must be kept consistent when bounding or fixing variables.
Conditioning on selecting item leaves capacity . Its fractional knapsack problem bounds that item's total interaction with the other selected items. Thus the ordered-pair quadratic objective is at most . Remove overweight items before defining their residual-capacity problems.
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.
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 .
Articles by others on the same topic
The Knapsack Problem is a classic optimization problem in computer science and mathematics that deals with selecting items to maximize the total value without exceeding a given weight limit. There are various forms of the Knapsack Problem, but the most commonly discussed are: 1. **0/1 Knapsack Problem**: In this version, you have a set of items, each with a specific weight and value. You must choose to include each item either completely or not at all (hence "0/1").