knapsack problem

views updated

knapsack problem A common example of an integer programming problem: a knapsack has volume V and there are an unlimited number of each of N different items. For i = 1,…,N one unit of item i has known volume Vi and known value mi. Integer numbers of the various items may be put into the knapsack and the objective is to pack as much value as possible into the knapsack without exceeding the total volume V.