The knapsack problem is a well-known optimization problem. Given a knapsack with a weight capacity and a set of items, each with its weight and value, the goal is to select the items to maximize the total value while ensuring the total weight does not exceed the capacity of the knapsack.
Write a genetic algorithm to solve the knapsack problem. A solved example is provided in lab 1.
You will be provided with an input file in the following format:
- First line: Number of test cases (must be at least 1) For each test case:
- Size of the knapsack
- Number of items For each item:
- Weight and value separated by a space
2 10 5 2 4 3 5 5 12 6 8 7 9 15 3 5 10 3 7 7 3
The output should display the selected items for each test case, along with the total value and total weight of the selected items.