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}$$

As $i$ ranges from $0$ to $n$ and $w$ ranges from $0$ to $W$, we have $O(nW)$ variables. Since $pack(\cdot,i)$ depends on $pack(\cdot,i−1)$, we process all variables in the increasing order of $i$. In the pseudocode below, we use a two-dimensional array pack of size $(W +1)×(n+1): pack[w][i]$ stores the value of $pack(w,i)$. The running time of this solution is $O(nW)$.

---

 $Knapsack([w_0,\ldots,w_{n−1}],W)$:
 $pack ←$ two-dimensional array of size $(W + 1) × (n + 1)$
 initialize all elements of $pack$ to false
 $pack[0][0] ←$ true
 for $i$ from $1$ to $n$:
 for $w$ from $0$ to $W$:
  if $w_{i−1} > w$:
   $pack[w][i] ← pack[w][i − 1]$
  else:
   $pack[w][i] ← pack[w][i − 1] ~~\text{OR} ~~pack[w − w_{i−1}][i − 1]$
 return $pack[W ][n]$

---

The two-dimensional table below presents the results of the call to $Knapsack([1,3,4],8)$ and uses “F” and “T” to denote false and true values.