Another Dynamic Programming Example

Below is the DP example from from Chapter 3 of Steven Halim's Competitive Programming 3. Code can be found on the book's web page. Steven Halim's own slides can be found on his web page.

Wedding Shopping (§3.5.1)

>> View Original Question on the UVa Online Judge

The abridged problem statement is as follows.

Given different options for C different types of garments (e.g., shirts, belts, and shoes) and a certain limited budget M, our task is to buy one of each garment. Each garment has up to 20 different options, with each option having a unique price K. We cannot spend more money than we have in our budget. You are to write an algorithm that finds the maximum possible amount you could spend. If there is no way to buy every garment, print "no solution". Limits:

For example, suppose M=20, C=3, and the garment prices were as follows:

For this sample case, the answer is $19: buy the shirt costing $8, the belt costing $10, and the shoes costing $1. Note that there are multiple ways to get to a sum of $19, but there is no way to get to $20.

Brute Force Solution

The brute force solution (a.k.a. "Complete Search" or "Backtracking") is to model the problem as a recursive function using "Base Case and Build".

Think about the different parts of the problem. Which parts could you solve incrementally?

In this problem, we can consider an incremental solution on the array of garments. Suppose we had a possible solution for the first m garments. How could we add one more garment and get a candidate solution for m+1 garments?

Now we need to figure out how to fully define the sub problem. We can do this using the index of the current garment being considered, and a number representing our current money.

The full recursion is defined below.

Although correct, this solution will run in exponential time. If there are 20 different garments and 20 different options for each garment, the worst-case running time of this algorithm is 2020 = 1026 (bigger than Avogadro's number)!

Top-Down DP

This is as simple as adding a DP cache indexed by a 2-tuple: the money M, and the current garment index g.

The new time complexity is going to be roughly proportional to the maximum size of our DP cache. If we start with M money and C different types of garment, then our DP cache is of size (M+1)*C, where the +1 accounts for the case when we have zero money. In the worst case when M=200 and C=20, this is just 4020 cases! That is an acceptable solution.

In Python, we can use the "Tuple" type directly as a key in a hash table.

In Java, there unfortunately is not a simple class we can use to make a hash table key out of a pair of integers. We have a few options:

  1. Create a mini-class that contains the pair of values and has a hashCode function.
  2. Transform the two values using a formula such as key = M + g*(maxM).
  3. Use a 2D array instead of a hash table for the cache.

Bottom-Up DP

The bottom-up solution to this problem is going to have the same asymptotic time complexity as the top-down solution, but it won't build a huge recursion stack and it will have a lower space bound.

In this problem, the idea for bottom-up is the same as in the top-down case, except you build the DP table/cache iteratively instead of recursively. Here is a chart from Steven Halim illustrating how the DP table would be populated, based on the example shown earlier.

Wedding Shopper Buttom-Up DP Table