The Knapsack Problem

The knapsack problem is in its essence that we want to fill a bag with a certain weight, and we have a set of objects and some set of objects sum should match the weight. Although this problem hasn’t been proven to be a hard problem, it is generally considered one.

If we have the goal weight b and the elements available to us expressed as a list of numbers which represent weights a1, a2, …, ai (for i elements), and another list of binaries corresponding to the list of weights e1, e2, …, ei we can express problem as following:

One proposed solution is the greedy algorithm which takes the largest object we can fit first and then keeps going until it’s not possible anymore, this algorithm is shown not to solve all instances of this problem. When the greedy algorithm can solve an instance of the knapsack problem it’s considered easy, such as a super-increasing solution.