C++ Reference: knapsack_solver

This documentation is automatically generated.

This library solves knapsacks:
   - 0-1 knapsack problems,
   - Multi-dimensional knapsack problems,
   - TODO(user) Multi-dimensional knapsack problem with n-ary conflicts
   between items.

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 ways is based on dynamic programming (mainly when weights, profits and dimensions are small, 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-dimension 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.:
   vector: profits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
   vector of vector: weights = [ [1, 2, 3, 4, 5, 6, 7, 8, 9],
                                 [1, 1, 1, 1, 1, 1, 1, 1, 1]]
   vector: capacities = [34, 4]
And then:
   KnapsackSolver solver(KnapsackSolver::KNAPSACK_MULTIDIMENSION_SOLVER,
                         "Multi-dimensional solver");
   solver.Init(profits, weights, capacities);
   int64 profit = solver.Solve();

Classes

BaseKnapsackSolver
KnapsackCapacityPropagator
KnapsackGenericSolver
KnapsackPropagator
KnapsackSearchNode
KnapsackSearchPath
KnapsackSolver
KnapsackState

Send feedback about...