A view of dynamic programming

canvas-army-knapsack-vintage-canvas-backpacks-girls

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.

Advertisements

One thought on “A view of dynamic programming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s