Solution: Maximum Amount of Gold

Solution 1: Analyzing the structure of a solution

Instead of solving the original problem, we will check whether it’s possible to fully pack our backpack with the gold bars. Given $n$ gold bars of weights $w_0,...,w_{n−1}$ (we switched to 0-based indexing) and an integer $W$, is it possible to select a subset of them of total weight $W$?

Exercise break: Show how to use the solution to this problem to solve the Maximum Amount of Gold Problem.

Assume that it’s possible to fully pack the backpack. There exists a set $S ⊆ {w_0,\ldots,w_{n−1}}$ of total weight $W$. Does it include the last bar of weight $w_{n−1}$?

Case 1: If $w_{n−1} \not\in S$, then a backpack of capacity $W$ can be fully packed using the first $n − 1$ bars.

Case 2: If $w_{n−1} ∈ S$, then we can remove the bar of weight $w_{n−1}$ from the backpack and the remaining bars will have weight $W − w_{n−1}$. Therefore, a backpack of capacity $W − w_{n−1}$ can be fully packed with the first $n − 1$ gold bars.

In both cases, we reduced the problem to essentially the same problem with a smaller number of items and possibly smaller backpack capacity. We therefore consider the variable $pack(w, i)$ equal to true if it is possible to fully pack a backpack of capacity $w$ using the first $i$ bars, and false, otherwise. The analysis of the two cases above leads to the following recurrence relation for $i > 0$,

$$pack(w,i) = pack(w,i − 1)~~ \text{or}~~ pack(w − wi−1,i − 1).$$

Note that the second term in the above formula does not make sense when $w_{i−1} > w$. Also, $pack(0,0) =$ true, and $pack(0,w) =$ false for any $w > 0$. Overall,

$$pack(w, i) = \begin{cases} \text{true} & \text{if }~~ i = 0 ~~\text{and}~~ w = 0 \\ \text{false} \\ LCS(i , j, k-1) \\ LCS(i-1, j-1, k-1)+1 & \text{if }~~ A[i]=B[j]=C[k] \end{cases}$$ ...