 problem, one has a set I = { 0,..., n} of items to be placed in a knapsack. Integer numbers a i and c i represent, respectively, the weight and the utility of each item i ∈ I. We assume that each item fits in the knapsack by itself and denote by b 