Objectives
To get familiar with greedy
To implement greedy algorithms to solve
To develop skills and understanding of practical uses of greedy
Grading
This practical will be graded out of 1 mark. If you are unable to explain any of the work that is assessed, you will be given 0. Continued issues with regard to the authorship of work may result in disciplinary action.
Useful Material
Greedy algorithm: https://en.wikipedia.org/wiki/Greedy_algorithm
Task 1: Coin change using a greedy strategy
Given some coin denominations, your goal is to make change for an amount, S, using the fewest number of coins. Write python code to find the fewest number of coins using the greedy approach. For example: Given coin denominations of 1c; 6c; 10c. If you want change for 14 cents, the greedy way is: 1x10, 4x1. (The optimal would be 2x6, 2x1)
For example:
Please enter denominations (separated by a comma): 1, 6, 10 Please enter the amount you want to give change for: 14 Your denominations:
1:10
4:1
Total coins: 5
Note: We covered the coin changing problem in tutorial 6, feel free to refer back to that as it may help you here
Does your answer for Part 1 always give the correct answer? If yes justify it to your neighbour, otherwise give a counter example.
Task 2a: Greedy thief (read file)
A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are n items available in the store and weight of the ith item is wi and its profit is pi. The thief cannot take a fraction of any item i.e. either the thief has to take the whole item or nothing. The items descriptions are given in the file items.txt.
First write a function, readFile(fileName), to read the file and save the data in an appropriate data structure. Return this data and print it.
For example:
Enter file name: items.txt
[[4, 13], [3, 4], [8, 5], [9, 10], [7, 11]]
Task 2b: Greedy thief
Add a function greedy(lst,capacity) to your code from task 2a that calculates the highest value items to choose that don’t exceed the capacity. Use this function to solve the problem based on the capacity entered by the user.
Hint: A sorting algorithm (like the ones you did last week that sorts according to columns) will be very useful here.
Hint: Notice how we sorted the data based on the value (column 1 from highest to lowest) to make it easier to apply the greedy algorithm.
For example:
Enter file name: items.txt Enter the capacity: 19 This is the item list
[[4, 13], [3, 4], [8, 5], [9, 10], [7, 11]]
This is the sorted item list
[[4, 13], [7, 11], [9, 10], [8, 5], [3, 4]]
Items Selected [4, 13]
[7, 11]
[8, 5]
Total value: $29
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of