# A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem
## 2 Background
### Knapsack Problem  
In layman's terms, a knapsack problem seeks to store a set of items into a knapsack with limited capacity. Therefore, one must choose a subset of the items based on some criteria. For example, the profit or weight to select the items that must go into the knapsack. In formal terms, let \(\vec{x}\in\mathbb{Z}_{2}^{n}\) be a binary-valued vector of \(n\) items, where each element \(x_{i}\in\vec{x}\) represents an item and its selection according to its position and value, respectively, for example, if there is a stock of three items and we choose the second one, we have \(\vec{x}=(0,1,0)^{\intercal}\). Likewise, let \(\vec{p}\in\mathbb{R}_{+}^{n}\) and \(\vec{w}\in\mathbb{R}_{+}^{n}\) be the profit and weight vectors directly related to the items, i.e., the \(i\)-th item has profit \(p_{i}\in\vec{p}\) and weight \(w_{i}\in\vec{w}\). Thus, this problem (widely known as the 0/1 Knapsack Problem) can be defined as  
\[\vec{x}_{*}=\operatorname*{argmax}_{\vec{x}}\{\vec{p}\cdot\vec{ x}\}, \tag{1}\] \[\text{s.t.}\quad\vec{w}\cdot\vec{x}\leq c,\] \[\text{with}\quad\vec{x}\in\mathbb{Z}_{2}^{n}\quad\text{and}\quad \vec{p},\vec{w}\in\mathbb{R}_{+}^{n}\]  
where \(c\in\mathbb{R}_{+}\) is the total capacity of the knapsack.  
Although many solving strategies can be found in the literature, the initial solvers for the knapsack problem were initially divided into two categories: exact methods and approximate ones. Exact methods provide optimal solutions but have limited applications due to their consumption of computational resources [31; 32]. Conversely, approximated methods make some assumptions to simplify the solving process to give usually suboptimal solutions [33].  
However, the advance in computing power and creativity has lead to extensive diversity of techniques that can be found nowadays, most of them hybrids. To provide a glance at such diversity, we mention some representative works. For example, Genetic Algorithms (GA) and Particle Swarm Optimization (PSO) have been used for solving the multidimensional KP [34; 35]. [PERSON] et al. proposed a Binary Particle Swarm strategy with a genetic operator, also for the multidimensional KP [36]. Another example of recent solving methods includes the one by [PERSON] and [PERSON], where the authors proposed using Gravitational Search (GSA) for solving the 0/1 KP [37]. Inspired by Quantum Computing, [PERSON] et al. proposed a novel method to solve the KP by using a Quantum-Inspired Evolutionary Algorithm [38]. Modifications to apparently simple ideas can also be found nowadays. For example, [PERSON] et al. solve the 0/1 KP by using Greedy Degree and Expectation Efficiency (GDEE) [39]. Some probabilistic models include Cohort Intelligence (CI) [40] and hybrid heuristics. For example, by using Mean Field Theory [41], [PERSON] et al. generated a probabilistic model capable of replacing a complex distribution of items with an easier one.  
The literature on the KP includes a wide variety of solution methods. For a thorough treatment, we refer the reader to the textbooks found in [42; 43]. Broadly speaking, the solution methods are of three types: exact methods, heuristic methods, and approximation algorithms (which are special heuristic methods that yield solutions of a guaranteed quality). The best exact methods are now capable of solving instances with thousands of items to proven optimality in reasonable computing times [32; 44; 45; 46]. However, it is possible to devise instances that are very challenging for exact methods [45]. For this reason, heuristics remain of interest.