ok i have a project where we have an amount of 2 dollars and 19 cents. we are trying to use dollars quarters nickles dimes and pennies and we have to find the minimum number of all to give back change. does any one have an idea were to start or how i would go about doing this?
7 2105
Starting at the largest denomination, find out how many will fit into that, then subtract that amount and start over with the next smallest denomination. It's what people do in real life, too.
Starting at the largest denomination, find out how many will fit into that, then subtract that amount and start over with the next smallest denomination. It's what people do in real life, too.
Note though that that method doesn't always yield the minimum number of coins;
imagine a silly country where they have denominations of 1, 10, 35 and 50.
The greedy approach for an amount of 70 yields three coins: 50, 10 and 10,
while the minimum number of coins would be 2: 35+35.
kind regards,
Jos
ps. lesson learned: greedy algorithms don't always result in an optimal solution ;-)
so what would be a better approach
so what would be a better approach
It depends on what you want to achieve; for denominations 1, 2.5, 5 the greedy
approach results in a minimum number of coins (it was designed that way ;-)
same as the 1, 2, 5 sequence, but if you want to solve that problem for any
ratio (as the silly one I sketched above) you'd better change your algorithm to
a dynamic programming approach.
kind regards,
Jos
The greedy algorithm I described above works for any currency set c where, for any coin/bill n in c, 2c(n) <= c(n+1). That is, it works for a currency set like our own where 2 pennies are smaller than or equal to a nickel, two nickels are smaller than or equal to a dime, two dimes are smaller than or equal to a quarter, etc...
When you have silly currency sets where 2c(n) is not always less than or equal to 2c(n+1), you need a better algorithm.
Back in the day, I designed an algorithm to solve this (without any knowledge of dynamic programming), but the efficiency was awful.
The greedy algorithm I described above works for any currency set c where, for any coin/bill n in c, 2c(n) <= c(n+1). That is, it works for a currency set like our own where 2 pennies are smaller than or equal to a nickel, two nickels are smaller than or equal to a dime, two dimes are smaller than or equal to a quarter, etc...
When you have silly currency sets where 2c(n) is not always less than or equal to 2c(n+1), you need a better algorithm.
Back in the day, I designed an algorithm to solve this (without any knowledge of dynamic programming), but the efficiency was awful.
Now because we gave the problem away, I think he should PROVE why the above works.
//Hands paper and pen.
///Start Clock
Now because we gave the problem away, I think he should PROVE why the above works.
//Hands paper and pen.
///Start Clock
Phew, you're clock's still running? ;-)
Sign in to post your reply or Sign up for a free account.
Similar topics
by: Jack Smith |
last post by:
Hello, any help appreciated with following problem. I figured out the
algorithm (I think), just having trouble proving it is optimal.
Suppose we are given n tasks each of which takes 1 unit...
|
by: lothar |
last post by:
re:
4.2.1 Regular Expression Syntax
http://docs.python.org/lib/re-syntax.html
*?, +?, ??
Adding "?" after the qualifier makes it perform the match in non-greedy or
minimal fashion; as few...
|
by: Federico Babelis |
last post by:
Hi:
Any could help my find how to create the code for the following algorythm:
In1: 10000000
In2: 00000000000
the algorythm runs and this is the output:
01A6DC6B07262F69
|
by: Earl Teigrob |
last post by:
Does someone have or know of an algorythm (method) that will delete all
files under a give directory and its subdirectories based on a wildcard
mask?
I can use this for one directory
for each...
|
by: Andrés Giraldo |
last post by:
Hi!
I'm trying to use a System.Security.Criptography function, it works on
my machine but when I publish the site, it gives me the following error:
Can't find a cryptographic service provider...
|
by: Bruce H |
last post by:
Hello,
I want to encrypt files using symmetric cryptography.
There are 4 algorythms that the frame supports.
Anybody knows which is the fastest algorythm?
(big files)
TIA
|
by: John Hazen |
last post by:
I want to match one or two instances of a pattern in a string.
According to the docs for the 're' module
( http://python.org/doc/current/lib/re-syntax.html ) the '?' qualifier
is greedy by...
|
by: EXI-Andrews, Jack |
last post by:
the '*' and '+' don't seem to be greedy.. they will consume less in
order to match a string:
('aa', 'ab')
this is the sort of behaviour i'd expect from
'(a+?)(ab)'
a+ should greedily...
|
by: plisho |
last post by:
Hello,
I'm writting a program in C++.
One part of my program is to compare two strings and as a result I have to have a number (range:0-1) which represents a similarity between those two strings....
|
by: CloudSolutions |
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
|
by: ryjfgjl |
last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
| |