The knapsack problem is a combinatorial optimization problem. It can be described as follows: given a fixed-size knapsack with a capacity to carry W amount of weight and a set of items that have a value and weight, find the best solution in a way to fill the knapsack with the most valuable items so that the total weight is less than or equal to W.
Here, we have an example:
| Item # | Weight | Value |
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
Consider that the knapsack can only carry a weight of 5. For this example, we can say that the best solution would be filling the knapsack with items 1 and 2, which together have a weight of 5 and a total value of 7.
There are two versions of this problem: the 0-1 version, in which we can only fill ...
