Waste less time on Facebook — follow Brilliant.
Introduction to Algorithms
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 | |
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?