Before introducing a greedy algorithm to find an optimal solution to the problem of the knapsack, it is appropriate to recall the main characteristics of any greedy technique. Any greedy technique proceeds iteratively. Starting from an empty solution, an element A is added to the partial solution under construction at each iteration. Of all the possible candidates to be added, element A is the most promising one—that is, if chosen, element A leads to a greater improvement of the objective function. It is clear that not all problems can be solved with this strategy, but only those for which it is possible to show that making the best choice at the moment leads to an optimal solution globally.
Let's look at an algorithm that ...
