In the Knapsack problem, our goal is to find the optimal combination of objects which are bound by a total weight W and which achieve the heighest profit / value (v). The problem can be applied to various real life applications such resource allocation problems.
Two variants of the Knapsack problem are considered. The Linear Knapsack Problem, where items have individual weights and values, and the Quadratic Knapsack Problem where there is an additional term in the objective functions, which represents the extra profit gained from choosing a particular combo of items (in our case pairs).