This library solves knapsack problems.
Problems the library solves include:
- 0-1 knapsack problems,
- Multi-dimensional knapsack problems,
Given n items, each with a profit and a weight, given a knapsack of
capacity c, the goal is to find a subset of items which fits inside c
and maximizes the total profit.
The knapsack problem can easily be extended from 1 to d dimensions.
As an example, this can be useful to constrain the maximum number of
items inside the knapsack.
Without loss of generality, profits and weights are assumed to be positive.
From a mathematical point of view, the multi-dimensional knapsack problem
can be modeled by d linear constraints:
ForEach(j:1..d)(Sum(i:1..n)(weight_ij * item_i) <= c_j
where item_i is a 0-1 integer variable.
Then the goal is to maximize:
Sum(i:1..n)(profit_i * item_i).
There are several ways to solve knapsack problems. One of the most
efficient is based on dynamic programming (mainly when weights, profits
and dimensions are small, and the algorithm runs in pseudo polynomial time).
Unfortunately, when adding conflict constraints the problem becomes strongly
NP-hard, i.e. there is no pseudo-polynomial algorithm to solve it.
That's the reason why the most of the following code is based on branch and
bound search.
For instance to solve a 2-dimensional knapsack problem with 9 items,
one just has to feed a profit vector with the 9 profits, a vector of 2
vectors for weights, and a vector of capacities.
E.g.:
Python:
profits = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
weights = [ [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
[ 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
]
capacities = [ 34, 4 ]
solver = knapsack_solver.KnapsackSolver(
knapsack_solver.SolverType
.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
'Multi-dimensional solver')
solver.init(profits, weights, capacities)
profit = solver.solve()
C++:
const std::vector<int64_t> profits = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const std::vector<std::vector<int64_t>> weights =
{ { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
const std::vector<int64_t> capacities = { 34, 4 };
KnapsackSolver solver(
KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"Multi-dimensional solver");
solver.Init(profits, weights, capacities);
const int64_t profit = solver.Solve();
Java:
final long[] profits = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
final long[][] weights = { { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
final long[] capacities = { 34, 4 };
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"Multi-dimensional solver");
solver.init(profits, weights, capacities);
final long profit = solver.solve();
Definition at line 94 of file KnapsackSolver.java.
1.10.0