The knapsack problem is a well-known optimization problem. It is encountered, for example, in packing shipping containers. A shipping container has a weight capacity which it can hold. Given a collection of items to be shipped, where each item has a value and a weight, the problem is to select the optimal items to pack in the shipping container.
This optimization problem can be defined as an objective with a constraint.
- Objective: Maximize freight value (sum of values of the selected items)
- Constraint: Total freight weight (sum of weights of the selected items) must be less than or equal to the container's capacity
We may also wish to add an additional constraint that specifies the maximum number of items that can be selected.