Description
An optimization algorithm by QCentroid
The Knapsack problem is a classic optimization problem. The problem is, essentially, the following:
We have a series of objects with two quantities associated to each, namely weight and value. We also have a knapsack that can carry up to a limited total weight. The problem is then to pick a subset of the objects to maximize the value in the knapsack without exceeding the total weight.
This problem is known to be NP-Complete, that is, it is really hard to find the optimal solution to it. If we have a graph with N nodes, the amount of possible solution grows exponentially. Comparing one solution to another one is easy, but finding the best one is similar to looking for a needle in a haystack.
In this example, we create a set of objects with weights and values to define the problem. Both series of values are introduced into the QCentroid API, who looks for the optimal solution in an easy way. The solution is showed afterwards.
Take into account that the hardest piece of this problem is finding the optimal solution. This step is completely addressed by the QCentroid, while the users / cabin boys and girls do not have to worry about it.
