Solve Knapsack Problems
DESCRIPTION:
Selects elements of x such that their sum is close to target.
USAGE: 
napsack(x, target, best=10)
REQUIRED ARGUMENTS:
x:
vector of the generators for the knapsack problem. The function attempts to find subsets of x whose sums are equal (or close to) target.
target:
scalar target value.
OPTIONAL ARGUMENTS:
best:
the desired number of solutions (or approximate solutions) to the problem.
VALUE:
matrix of logical values, of size length(x) by best. Each column tells which elements of x are contained in one of the best subsets. Thus, a column of the result can be used to subscript x to obtain a subset.
NOTE:
The knapsack problem is NP-complete, and the algorithm is exponential in time and space complexity. If n is the length of x, then the algorithm requires time on the order of 2^(n/2) and space on the order of 2^(n/4). Problems with n < 50 can be readily solved by this function. Remember that both time and space requirements increase very rapidly with problem size!

The solutions produced may not include all subsets that can generate solutions with a certain error. It is guaranteed to produce an exact solution if one is possible, but may not find all of a number of exact solutions.

DETAILS:
The napsack function solves a specialization of the classical problem. The c and a vectors are constrained to be equal and the solutions are close to target rather than less than or equal to it. Solutions are allowed to be slightly larger than target. Results are currently computed to single-precision accuracy only.
BACKGROUND:
The classical knapsack problem is to maximize cy such that ay is less than target, where y is a vector of zeros and ones. The name derives from the problem of a hiker deciding which items to take in order to maximize utility while keeping the pack less than a maximum weight. Uses of the knapsack include budgeting and project selection. Additionally, integer programming problems can often be reduced to a knapsack problem.
REFERENCES:
Schroeppel, R. and Shamir, A. (1979). A T*S^2 = O(2^n) Time/Space Tradeoff for Certain NP-Complete Problems. Twentieth Symposium in Foundations of Computer Science, October 1979.

Salkin, H. M. (1975). Integer Programming. Addison-Wesley, Reading, Mass.

SEE ALSO:
mstree .
EXAMPLES: 
# given areas of the states, find subsets of them
# with approximately 1/2 the total area of the country
state.area <- state.x77[,"Area"]
state.half <- napsack(state.area, sum(state.area)/2)
crossprod(state.half, state.area) # areas of the subsets