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.
In the unbounded knapsack problem, each item type may be used any nonnegative integer number of times. With positive integer weights , values and capacity , maximize subject to and .
A dynamic programming recurrence for capacity-at-most value is . Evaluate capacities in increasing order so repeated uses are available. With weights three and five, values four and seven, and capacity ten, two weight-five items give value fourteen. A zero-weight positive-value item would make the objective unbounded, explaining the positive-weight hypothesis.
The bounded knapsack problem adds per-type upper limits to the integer knapsack problem. It interpolates between 0-1 knapsack problem () and the unbounded knapsack problem.
Processing types one at a time gives . The previous-type index prevents the recurrence from exceeding the allowed count. For large , splitting counts into power-of-two bundles and a final remainder reduces the bounded type to logarithmically many 0-1 knapsack problem items while preserving every allowable count.
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.
Assign each item to neither bag or exactly one of two bags, respecting both capacities and maximizing total value. With nonnegative integer capacities , a dynamic programming state indexed by the item prefix and both capacities gives 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 .
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").