Uses of Package
com.google.ortools.algorithms
Packages that use com.google.ortools.algorithms
-
Classes in com.google.ortools.algorithms used by com.google.ortools.algorithmsClassDescription
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.Enum controlling which underlying algorithm is used.
This enum is passed to the constructor of the KnapsackSolver
object.