Greedy Algorithm Practice Problems Online

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

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 $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?

Given a set of denominations $D$ , we want to make coin change for a specified amount $M$ , 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 $M$ .

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

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

Introduction to Algorithms

Concept Quizzes

Greedy Algorithm