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
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
