Introduction
Multiple knapsack problem is a famous problem in combinatorial optimization. Suppose you have a set of objects, each of which has a certain weight and value. We are looking for how to allocate objects to knapsacks in such a way that the total weight of the selected objects is smaller than the capacity of the Knapsacks, and also their total value is maximized.
Instruction of using online solver of multiple knapsack problem
The GUI of the online solver of the multiple knapsack problem is as follows.
Problem input
To find the optimal solution to the multiple knapsack problem, the required inputs are as follows:
n: the number of items available.
m: the number of available knapsacks.
depth: If we are looking for the optimal solution, the value of -1 should be considered. If obtaining an approximate answer is sufficient, the number of necessary repetitions can be entered as a natural number.
weight: The vector has n+1 components that determine the weight of each product or item. The first component is equal to zero.
profit: vector has n+1 components that determine the profit of each product or item. The first component is equal to zero.
capacity: The vector has m+1 components and determines the capacity of each knapsack. The first component is equal to zero.
Note: It is not possible to put one product or item in more than one knapsack. In other words, a product or item is either not in any knapsack or is in one of the knapsacks.
Example: Consider the knapsack problem for two knapsack and 10 items with the following specifications.
If the capacity of the first and second knapsack is 125 and 146 respectively. Solve the optimal solution to this problem.
Solution: Entering information in the online solver for the multiple knapsack problem is as follows.
After entering the data, we click on the RUN button.
The result of running the algorithm is as follows.
In the output part of the algorithm, when “Optimal solution found” is reported, it means that this problem has an optimal solution. The numbers printed after this statement indicate which knapsack each item is placed in. If the number is zero, it means that the corresponding item is not in any of the knapsacks. If the number is 1, it means it is in the first knapsack, and if the number is 2, it means it is in the second knapsack.