An algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage is called a greedy algorithm. For example, the Knapsack Problem: 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. can be "solved” by a greedy algorithm which repeatedly choose an item having the highest value or some other factor defined on weight and value until the bag is full or none of the rest of the items can be added to the bag. Although greedy algorithms often cannot produce an optimal answer to problems, the solutions obtained are usually satisfactory. In this project, we are going to use greedy algorithms to solve the knapsack Problem. The selection of items in the algorithms is performed on a priority queue. Implementation Tasks: 1. (5 points) Implementation of a Java class for items. You are required to include not only the weight and value of the item, but also an ID to distinguish the item from the others, and a particular factor (double type) which indicates the priority of the item. Appropriate constructors should be defined. 2. (20 points) You are required to implement a Java class for maximum binary heaps. Each element in the heap is an item, more precisely, in Java, it should be the reference of an item object. The items are organized according to their priority factors. You are required to provide appropriate methods for creating a heap, adding a new item to the heap, and deleting the item of the highest priority from the heap. 3. (5 points) First greedy algorithm to solve the knapsack Problem: We consider the items defined as follows: Item ID (int) 0 Weight (double) 23 Value (double) 505 1 26 352 2 20 458 3 18 220 3 4 4 32 354 5 27 414 6 29 498 7 26 545 8 00 30 473 9 27 543
The weight limit of the bag is 67. Please implement a greedy algorithm which iteratively consider the item with the highest value and add it to the bag if the limit is not reached until all items are checked. Hence, the priority factor defined here is the item value. Please display the selected items. 4. (5 points) Second greedy algorithm to solve the Knapsack Problem: We consider the same items but define the priority as the additive inverse of the weight, i.e., lighter items are preferred. Please display the selected items. 5. (5 points) Third greedy algorithm to solve the knapsack Problem: We consider the same items but define the priority as the ratio of value and weight, i.e., value/weight. Please display the selected items.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!