Solution: Maximum Value of the Loot

Solution 1: Recursive algorithm

Let’s define the price of a compound $i$ as $c_{i}$/$w_{i}$. A natural strategy for the thief is to keep taking as much of the priciest (most expensive) compound as possible. To prove that this strategy leads to an optimal solution, let’s consider the most expensive compound $m$. What is the maximum amount $a$ of the $m$-th compound that the thief can take into his backpack? First, it should fit into the backpack: $a ≤ W$. Second, it should not exceed the available amount of the $m$-th compound: $a ≤ w_{m}$. Therefore, $a$ = $min\{w_{m},W\}$. We claim that there is an optimum solution containing $a$ pounds of the $m$-th compound.

To prove it, consider an optimum solution $u_{1},\ldots,u_{n}$ that maximizes the amount $u_{m}$ of the most expensive $m$-th compound among all optimum solutions ($u_{i}$ stands for the amount of the $i$-th compound). If $u_{m} = a$, then there is nothing to prove. Otherwise, $u_{m} < a$. Therefore, $u_{m} < w_{m}$ and $u_{m} < W$. Consider the following two cases: