The family of the feasible solutions for a Knapsack with positive coefficients, , is an independence system over . In some cases, for instance when all the a i have the same value, this independence system is a matroid over . The authors will say then that the knapsack is greedy solvable. In the first part of this paper they study the conditions for a knapsack to be greedy solvable. The authors present necessary and sufficient conditions, verifiable in polynomial time, for to be a member of a family of matroids over . In the second part of the paper they study a family of matroidal relaxations for the knapsack problem. The authors prove that those relaxations dominate the usual linear programming one for this problem and they present some computational results in order to illustrate that domination.
