Solving a big problem by combining small decisions

series: dynamic programming

Imagine you are a merchant in 17-th century Venice. You have about hundred containers in your warehouse, containers with goods of a different nature. Each container has a different weight, and a different value.

While planning your next business trip, you want to fill your cargo ship with the most profitable items. Although you would like to bring it all, your ship has a limited capacity. Which containers would you take first?

Unable to decide, you ask for help from Dr. Bellman, a famous computational scientist of your time. Dr. Bellman does not reveal to you an optimal configuration, but explains the logical steps for solving this problem - an algorithm.

 Suppose that you have only 3 containers A, B, and C with respective weights 1, 2 and 3 tons. The value of container 1 is 60 lire, the value of container 2 is 100 lire, and the value of container 3 is 120 lire. The ship can carry only 5 tons of merchandise.

Note that if you were allowed to take only a fraction of a container, the solution is quite simple. You would calculate the value density for each container, that is value per unit of weight. Then load the container with the most value-dense items first, and fill the space to a full with parts of remaining containers, as in the example below.

However, this does not produce the best solution, if you are disallowed to take a fraction of a container. In this case, being greedy might leave you with a sub-optimal result. In this case, you would be better by adding a less value-dense item, to improve an overall cargo value.

To solve this problem we need to meditate on a final optimal solution which includes for example item B with the weight of 2 tons. If this is an overall optimal result for the total capacity of 5 tons, then the (5-2)=3 ton-capacity solution must also be optimal, but not include item B.

This suggests that we need to try adding containers one-by-one, and we need to have the best solutions available for each unit of weight: 1,2,3,4, to a total of maximum capacity 5. That is because we would look at the best solution for 3 tons when trying to add container of weight 2.

To summarize, in order to choose the best value for 5 ton capacity, calculate the best value for 4 tons, and then consider if you can improve it by adding each of available containers. How do you calculate the best value for 4 tons? Calculate the best value for 3 tons and try to improve it when the capacity grows.

In practice it all boils down to filling a table: left-to-right, top to bottom. Each row corresponds to a container, and each column represents a growing capacity of a cargo ship. Each cell in this table holds the best value for each of 1,2,3,4,5 capacities and we try to improve it by adding one of 3 available items. At each step we choose between adding and not adding a current container, and choose an option with the best total value. In the last cell, we would have the best possible total value for 5 tons.

That is a general algorithm for solving the best-value cargo problem, which we also call the knapsack problem - in case you need to find an optimal solution to fill a knapsack, not a ship. 

Now that you understand the algorithm, you can create the best-valued cargo any time you need it.