CLRS 16.2: Greedy algorithms
Problem 16.2-7
Suppose you are given two sets \(A\) and \(B\), each containing \(n\) positive integers. You can choose to reorder each set however you like. After reordering, let \(a_i\) be the \(i\)-th element of set \(A\), and let \(b_i\) be the \(i\)-th element of set \(B\). You then receive a payoff of \(\prod_{i} a_i^{b_i}\). Give an algorithm that will maximise your payoff.
Intuitively, it seems that sorting the sets \(A\) and \(B\) will maximise the payoff, by giving the greater exponents to the greater bases. We can prove that this is optimal.
Let set \(A = {a_1,a_2,\ldots,a_n}\) be in sorted order. Suppose \(B\) is ordered such that there is some \(i,j\) such that \(i<j\) but \(b_i > b_j\). Note that the product \(a_i^{b_i}{a_j}^{b_j}\) is a factor of the final payoff, and we can just try to improve this factor. If we swap the positions of \(b_i\) and \(b_j\), the new product \(a_i^{b_j}a_j^{b_i}\) changes by a factor of \(a_i^{b_i-b_j}a_j^{b_j-b_i} > a_i^{b_i-b_j}a_i^{b_j-b_i} = 1\), and thus increases.
If \(B\) is in sorted order, then no such \(i,j\) will exist, and we can no longer improve the payoff by this process anymore. Thus sorting \(B\) must then provide the optimal payoff (Noting that an optimal payoff clearly exists).
Problem 16.2-6
Show how to solve the fractional knapsack problem in \(O(n)\) time.
I was quite surprised to learn that there is an \(O(n)\) solution, but it kind of makes sense when comparing it to finding order statistics.
The classic \(0-1\) knapsack problem has a thief robbing a store with \(n\) items. The \(i\)-th item is worth \(v_i\) dollars and weighs \(w_i\) pounds, where \(v_i\) and \(w_i\) are integers. The thief wants to maximise the value of his load, but he can carry at most \(W\) pounds in his knapsack, where \(W\) is an integer.
In the fractional knapsack problem, the thief can take any fraction of each item. It is actually an easier problem, because we can greedily select the item with the best value-for-weight ratio, \(v_i/w_i\). Sorting the items by this ratio will take \(O(n\,log \,n)\).
However, intuitively we are not particularly interested in the order of the items, so sorting is extra effort. Since we can only carry \(W\) pounds, as long as a set of the highest value-for-weight items have total weight less than \(W\), we are always taking the whole set (regardless of order). I found the following solution online:
We can find the item of median value-for-weight in \(O(n)\) (using quickselect), and sum the weight of all items with value-for-weight greater than the median as \(M\). If \(M > W\), then we know that the solution lies in taking items only among this collection, i.e. we are solving the fractional knapsack problem on input of size \(n/2\). If \(M < W\), then we take all \(M\) pounds of high value-for-weight items, and solve the fractional knapsack problem again on the remaining \(n/2\) items. We have a runtime of \(T(n) = T(n/2) + O(n)\), which gives a total runtime of \(O(n)\).