The knapsack problem is very real: any time you fly with a cheap airline with cabin baggage only, things get complicated. Do I really need this? I could just leave my DSLR at home and use my phone for pictures, right?
These are statements that express the potential value of an item and the considerations regarding its weight (or volume on these flights), and we typically want to bring the most valuable (to us) items on a trip. While this smells like an algorithmic problem, it's far from simple. Let's start with the goal:
Given n items (with weights and values), find the subset of items providing the highest value without exceeding the knapsack's capacity, W.
Derived from this, the way to implement the solution can be constructed as follows: as an exhaustive search algorithm, every possible solution can be the best solution. However, this will only become clear once all solutions are evaluated. Thus, let's generate every possible...
