Solution: Maximum Value of the Loot

Solutions for the Maximizing the Value of the Loot Problem.

Solution 1: Recursive algorithm

Let’s define the price of a compound ii as cic_{i}/wiw_{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 mm. What is the maximum amount aa of the mm-th compound that the thief can take into his backpack? First, it should fit into the backpack: aWa ≤ W. Second, it should not exceed the available amount of the mm-th compound: awma ≤ w_{m}. Therefore, aa = min{wm,W}min\{w_{m},W\}. We claim that there is an optimum solution containing aa pounds of the mm-th compound.

To prove it, consider an optimum solution u1,,unu_{1},\ldots,u_{n} ...