Computer Science

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 580kg580kg 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.50 per gram

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

There are nn female dancers with heights p1,..,pnp_1,..,p_n and nn male dancers with heights s1,...sns_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?

Given a set of denominations DD, we want to make coin change for a specified amount MM, which we will assume is achievable with the denominations we have access to.

If we want to use as few coins as possible, the greedy approach would be to build a pile of coins by always adding the largest coin which doesn't make the total value of the pile larger than MM.

This approach doesn't always work, but for some denominations it always gives the optimal solution.

For which set of coin denominations DD will this approach correctly give us an optimal solution?

×

Problem Loading...

Note Loading...

Set Loading...