Algorithm 632

Algorithm 632: A program for the 0-1 multiple knapsack problem. Given n items, each having a profit p j and a weight w j , and m containers (knapsacks), each having a capacity k i , the 0-1 multiple knapsack problem can be informally described as that of assigning items to the knapsacks such that the total profit of the assigned items is a maximum, the total weight assigned to each knapsack does not exceed its capacity and each item is either assigned to one of the knapsacks or rejected. The paper presents a program to solve the problem through a particular depth-first tree-search technique making use of a lower bound to determine which branches to follow in the decision tree and an upper bound to limit the number of explored nodes. The program allows one to terminate the execution after a specified number of iterations (backtrackings), getting the best solution currently found.