Using C++:

Algorithms Knapsack Project (100 pts] 1 Introduction The objective of this project is to (1) correctly implement the greedy-heuristic and exhaustive approaches to solving the Knapsack Problem (2) measure their run times and (3) compare these with their asymptotic complexities. Your program should assume the input file is formatted as follows: 15 4 10 20 1 2 6 13 3 7 The first line contains the weight capacity of the knapsack. The second line contains n, the number of unique items. Each of the next n lines contains each item's weight followed by its value (the first item listed being item 1, the last being item n, etc). Assume all items' weights and values are integers. Your output should report the total value of items carried on the first line, and on the second line the items are used to achieve this. For consistency with our solutions, your output should list items in order by their item number. The optimal output for the example above would be: 29 1 2 4 Algorithm 1 Exhaustive Solution Input: knapsack weight capacity W, number of items n, list of (weight, value) pairs items - Let PowerSet = list of all subsets of items knapsack = { } best Value 0 for each subset in Power Set do subset Value 0 subset Weight = 0 for each item in subset do subset Value += item.value subset Weight += item.weight if subset Weight best Value then best Value subset Value knapsack = subset return knapsack = Algorithms Knapsack Project (100 pts] 1 Introduction The objective of this project is to (1) correctly implement the greedy-heuristic and exhaustive approaches to solving the Knapsack Problem (2) measure their run times and (3) compare these with their asymptotic complexities. Your program should assume the input file is formatted as follows: 15 4 10 20 1 2 6 13 3 7 The first line contains the weight capacity of the knapsack. The second line contains n, the number of unique items. Each of the next n lines contains each item's weight followed by its value (the first item listed being item 1, the last being item n, etc). Assume all items' weights and values are integers. Your output should report the total value of items carried on the first line, and on the second line the items are used to achieve this. For consistency with our solutions, your output should list items in order by their item number. The optimal output for the example above would be: 29 1 2 4 Algorithm 1 Exhaustive Solution Input: knapsack weight capacity W, number of items n, list of (weight, value) pairs items - Let PowerSet = list of all subsets of items knapsack = { } best Value 0 for each subset in Power Set do subset Value 0 subset Weight = 0 for each item in subset do subset Value += item.value subset Weight += item.weight if subset Weight best Value then best Value subset Value knapsack = subset return knapsack =