knapsack_rational, a C code which solves the rational knapsack problem, in which a knapsack of limited weight capacity is filled with profitable items. This variation of the 0/1 knapsack problem allows a fractional part of an item to be included in the knapsack. The result is an upper bound on the maximum possible profit for the 0/1 knapsack problem.
The rational knapsack problem is a generalization of the 0/1 knapsack problem. It is mainly used to derive a bounding function for the 0/1 knapsack problem.
The 0/1 knapsack problem is as follows:
Given:
a set of N objects,
a profit P(I) and weight W(I) associated with each object,
and a weight limit MASS_LIMIT,
Determine:
a set of choices X(I) which are 0 or 1, that maximizes the profit
P = Sum ( 1 <= I <= N ) P(I) * X(I)
subject to the constraint
Sum ( 1 <= I <= N ) W(I) * X(I) <= MASS_LIMIT.
By contrast, the rational knapsack problem allows the values X(I) to be any value between 0 and 1. A solution for the rational knapsack problem is known. Arrange the objects in order of their "profit density" ratios P(I)/W(I), and then take in order as many of these as you can. If you still have "room" in the weight constraint, then you should take the maximal fraction of the very next object, which will complete your weight limit, and maximize your profit.
If should be obvious that, given the same data, a solution for the rational knapsack problem will always have a profit that is at least as high as for the 0/1 problem. Since the rational knapsack maximum profit is easily computed, this makes it a useful bounding function.
The information on this web page is distributed under the MIT license.
knapsack_rational is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.
combo, a C code which includes many combinatorial routines.
knapsack_01_brute, a C code which uses brute force to solve small versions of the 0/1 knapsack problem;