An exact algorithm for the knapsack sharing problem with common items

摘要

We are concerned with a variation of the knapsack problem as well as of the knapsack sharing problem, where we are given a set of n items and a knapsack of a fixed capacity. As usual, each item is associated with its profit and weight, and the problem is to determine the subset of items to be packed into the knapsack. However, in the problem there are s players and the items are divided into s + 1 disjoint groups, Nk (k = 0, 1,..., s). The player k is concerned only with the items in No U Nk, where No is the set of 'common' items, while Nk represents the set of his own items. The problem is to maximize the minimum of the profits of all the players. An algorithm is developed to solve this problem to optimality, and through a series of computational experiments, we evaluate the performance of the developed algorithm. ((c)) 2004 Elsevier B.V. All rights reserved.