Computer Science

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

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$$. 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 $$D$$ will this approach correctly give us an optimal solution?

×