Let P be a problem. To solve P, we have a set of resources R which contains n elements { R(1), R(2), … R(n) }. Each subset of R (even empty one) can or cannot solve P but in case it can, there’s a cost of the solving. We have to choose a subset so that the solving cost is best (min or max).

**We’ll consider the issue in term of dynamic programming.**

There should be a way to decompose the problem P into m atomic problems: P(1), P(2), … P(m) (*)

Let DP(i, j) represents the best cost when we have to solve the composition problem:

{ P(1), P(2), … P(j-1), P(j) }

by using some resources from the set:

{ R(1), R(2), … R(i-1), R(i) }

The value of DP(i, j) comes from 2 options:

**If R(i) is not used**, of course we have a candidate value: DP(i, j) = DP(i-1, j).

**If R(i) is used**, then we must detect the role of R(i). In other words, which atomic problems can be solved by R(i). The decomposing (*) is very important so that in this case, we are able to assign R(i) to solve k (k > 0) atomic problems: P(j-k+1), … P(j) hence a candidate value is:

DP(i, j) = DP(i-1, j-k) + EXTRA_COST

EXTRA_COST is the cost of solving P(j-k+1) … P(j) by using R(i). In typical cases, k is just 1, 2 or 3 so this cost should be calculated easily and directly. If there are many values of k, we will have many candidate values for DP(i, j). For example:

if k=1

then DP(i, j) = DP(i-1, j-1) + EXTRA_COST = C1

if k=2

then DP(i, j) = DP(i-1, j-2) + EXTRA_COST = C2

if k=3

then DP(i, j) = DP(i-1, j-3) + EXTRA_COST = C3

and so on. But please note that sometimes we can recognize the trend of C1, C2, C3; then the listing of many candidate values is unnecessary.

How about DP(0, j)? This is a special case and we have to calculate manually, depend on our specific issues.

Finally, DP(i, j) = min or max of all candidate values.

In some specific issues, there might be a couple of optimization. For instance, i is always less than or equal j so we do not need to calculate DP(i, j) with i > j.

**Now let’s take an example: the Knapsack issue.**

The problem P is the volume V of the Knapsack. The set of resources R is the objects. A subset of objects can solve P if its total volume is not greater than V, and the cost is its total value. Here we want the cost is max.

Obviously, P will be decomposed into V atomic problems. Each problem is one unit of volume. We have:

DP(i, j) = max( DP(i-1, j), DP(i-1, j - iVolume) + iValue ) iVolume/iValue is the volume/value of the object i. If j < iVolume then only DP(i-1, j) is considered.

As we can see, the object i can solve more atomic problems, not just iVolume problems, but: iVolume+1 problems, iVolume+2 problems, … however the EXTRA_COST is always = iValue; and the trend of DP is descending; therefore those other atomic problems are not considered.

## One thought on “A view of dynamic programming”