Maximize Payoff by Greedy Reordering

Source: CLRS, Introduction to Algorithms, 2nd Edition, Page 384, Problem 16.2-7

Problem:
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=1}^{n}{a_i^{b_i}}\). Given an algorithm that will maximize your payoff. Prove that your algorithm maximizes the payoff, and state its running time.

Solution:
Greedy Algorithm: Let the set \(\{a_i\}\) be sorted so that \(a_1 \ge a_2 \ge \ldots \ge a_n\) and set \(\{b_i\}\) be sorted so that \(b_1 \ge b_2 \ge \ldots \ge b_n\). Pair \(a_i\) with \(b_i\). This is the required solution.

Complexity:
If the two sets \(A\) and \(B\) are already sorted, the time complexity is \(O(n)\).
If the sets are not sorted, then sort them first and the time complexity is \(O(n\log n)\).

Proof:
Suppose the optimal payoff is not produced from the above solution. Let \(S\) be the optimal solution, in which \(a_1\) is paired with \(b_p\) and \(a_q\) is paired with \(b_1\). Note that \(a_1 \gt a_q\) and \(b_1 \gt b_p\).

Consider another solution \(S'\) in which \(a_1\) is paired with \(b_1\), \(a_q\) is paired with \(b_p\), and all other pairs are the same as \(S\). Then \[\frac{\text{Payoff}(S)}{\text{Payoff}(S')}=\frac{\prod_{S}\hspace{2 mm} a_i^{b_i}}{\prod_{S'}\hspace{2 mm}a_i^{b_i}}=\frac{(a_1)^{b_p} (a_q)^{b_1}}{(a_1)^{b_1} (a_q)^{b_p}}=(\frac{a_1}{a_q})^{b_p - b_1}\] Since \(a_1 \gt a_q\) and \(b_1 \gt b_p\), then \(\text{Payoff}(S) / \text{Payoff}(S') \lt 1\). This contradicts the assumption that \(S\) is the optimal solution. Therefore \(a_1\) should be paired with \(b_1\). Repeating the argument for remaining elements, we can get the result.

0-1 Knapsack Problem

Problem:
A thief robbing a store finds \(n\) items; the \(i\)th item is worth \(v_i\) dollars and weights \(w_i\) pounds, where \(v_i\) and \(w_i\) are integers. He wants to take as valuable a load as possible, but he can carry at most \(W\) pounds in his knapsack for some integer \(W\). Which items should he take?

Analysis:
There are two versions of this problem: fractional knapsack problem and 0-1 knapsack problem.

1. Fractional knapsack problem: the items can be broken into smaller pieces, and the thief can take fractions of items.
2. 0-1 knapsack problem: the items may not be broken into smaller pieces, and the thief must decide whether to take an item or leave it (binary choices).

For fractional knapsack problem, greedy algorithm exists and the problem can be solved in \(O(n\log n)\) time based on sorting. And a better approach may take \(O(n)\) time for the worst case based on linear-time SELECT algorithm.

For 0-1 knapsack problem, no greedy algorithm exists and we need turn to dynamic programming approach. The algorithm will take \(O(nW)\) time.

Solution:
Define \(c[i,w]\) to be the optimal value for items \(1,2,...,i\) and maximum weight \(w\). There are following recursive relations:
\[c[i,w]=\begin{cases}0, & i=0\text{ or }w=0\\c[i-1,w], & w_i\gt w\\ \max\{v_i+c[i-1,w-w_i], c[i-1,w]\}, & i>0 \text{ and }w_i \le w\end{cases}\] We can have the pseudocode:

DP_01_Knapsack(value, weight, W)
   assert value.length = weight.length
   n ← value.length
   for w ← 0 to W:
      c[0,w] ← 0
   for i ← 1 to n:
      c[i,0] ← 0
      for w ← 1 to W:
         c[i,w] ← c[i-1,w]
         if weight[i] ≤ w and value[i]+c[i-1,w-weight[i]] > c[i-1,w]:
            c[i-1,w] ← value[i]+c[i-1,w-weight[i]]

The set of items to take can be deduced from the table, starting at \(c[n,W]\) and tracing backwards where the optimal values came from. If \(c[i,w]=c[i-1,w]\), then item \(i\) is not part of the solution, and we are continue tracing with \(c[i-1,w]\). Otherwise item \(i\) is part of the solution, and we continue tracing with \(c[i-1,w-w_i]\).

References:

Dynamic Programming Solution to the 0-1 Knapsack Problem