The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
We will solve the 0-1 Knapsack type of this problem with the following methods:
-
Simulated Annealing
-
Genetic Algorithm
-
Ant Colony Algorithm
-
Artificial Bee Colony Algorithm
You can find sample test files in Datasets.
| Dataset | Optimal Value |
|---|---|
| test1.txt | 41494 |
| test2.txt | 191977 |
| test3.txt | 66029 |
| test4.txt | 973950 |
| test5.txt | 236490 |
| test6.txt | 2338497 |
| test7.txt | 380618 |
| test8.txt | 2015213 |
| test9.txt | 930173 |
| test10.txt | 7872942 |