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.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

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. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

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

. 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 Sea Ports. Here are the classes and their instance variables we wish to define:

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