Waste less time on Facebook — follow Brilliant.
×

Introduction to Algorithms

Greedy Algorithm

     

A thief walks into a house. To his surprise, the thief discovers that the owner of the house has pulverized all his precious metals into fine dust. The thief can thus scoop whatever amount he wants. Because of the density of the precious metals and the amazing strength of his back pack, it can accommodate a total of \(580kg\) dust.

In the house there is 

1
2
3
4
5
100kg of gold dust worth 39.95$ per gram
100kg of platinum dust worth 32.1$ per gram
200kg of rhodium dust worth 21.54$ per gram
300kg of palladium dust worth 17.75$ per gram
500kg of silver dust worth 0.5$ per gram

If he packs his bag optimally, how much money worth of metals will he walk out with?

View solution
by Brilliant Staff

There are \(n\) female dancers with heights \(p_1,..,p_n\) and \(n\) male dancers with heights \(s_1,...s_n\). The problem is to assign each male dancer to a female dancer and minimize the average difference between the height of the male and the female. Consider the greedy solution to this problem. What is the overall complexity(including sorting) of this algorithm?

View solution
by Brilliant Staff

Given a set of denominations \(D\), we want to make coin change for a specified amount \(M\). The greedy approach would be to keep using the largest possible denomination less than the amount we have at any point. It turns out that this sometimes does yield an optimal solution. For which set of coin denominations \(M\) will this approach correctly give us an optimal solution?

View solution
by Brilliant Staff
×

Problem Loading...

Note Loading...

Set Loading...