Skip to content

Latest commit

 

History

History
442 lines (313 loc) · 18.1 KB

introduction.md

File metadata and controls

442 lines (313 loc) · 18.1 KB

Dynamic Programming

What is Dynamic Programming?

Calculate the answer to the following expression: 34 + 5! + (50 * 9)

Now calculate the answer to the following expression: 34 + 5! + (50 * 9) + 17

It was much easier to calculate the second expression than it was the first, but why?

You didn't need to recalculate the entire second expression because you memorized the value of the first expression and used it for a later time.

That's exactly what dynamic programming is: remembering information in order to save some time later on.

What is Dynamic Programming (Mathematical definition)

Dynamic programming is a method for solving complex problems by breaking it down into a collection of simpler subproblems.

Dynamic programming problems exhibit two properties:

  • Overlapping subproblems
  • Optimal substructure

So what exactly does this mean? Let's take a look at some examples.

Fibonacci Sequence

The Fibonacci sequence is one in which a term in the sequence is determined by the sum of the two terms before it.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

We say that the nth Fibonacci number can be found by Fn = Fn-1 + Fn-2, where F0 = 1 and F1 = 1

Let's say we wanted to write a recursive function for this sequence to determine the nth Fibonacci number.

// This function will return the nth Fibonacci number
public int fib( int n )
{
    // Base case: the first two Fibonacci numbers are 1
    if ( n == 0 || n == 1 )
        return 1;
    return fib( n - 1 ) + fib( n - 2 );
}

What will be the function calls if we wanted to determine fib( 5 )?

fib( 5 )
fib( 4 ) + fib( 3 )
fib( 3 ) + fib( 2 ) + fib( 3 )
fib( 2 ) + fib( 1 ) + fib( 2 ) + fib( 3 )
fib( 1 ) + fib( 0 ) + 1 + fib( 2 ) + fib( 3 )
1 + 1 + 1 + fib( 2 ) + fib( 3 )

Is it necessary to compute fib( 2 ) and fib( 3 )?

img

The above tree represents the function calls for fib( 5 )

Notice that when we calculate fib( 4 ) we also calculate the value of fib( 3 )

When we call fib( 5 ), it calls fib( 3 ), but if we already have the value of that function call from before, there's no need to recompute it.

Since fib( 5 ) asks us to call the function fib( 3 ) multiple times, we have found an overlapping subproblem - a subproblem that is reused numerous times, but given the same result each time it's solved.

fib( 3 ) will give us the same result no matter how many times we call it.

Rather than solving these overlapping subproblems every time, we can do the following:

  • solve the subproblem once and save its value
  • when you need to solve the subproblem again, rather than going through all the computation to do the solving, return the memorized value
int[] dp = new int[ SIZE ]; // all values initialized to 0
public int fib( int n )
{
    if ( n == 0 || n == 1 )
        return 1;
    if ( dp[ n ] != 0 )
        return dp[ n ];
    return dp[ n ] = fib( n - 1 ) + fib( n - 2 );
}

Pascal's Triangle

In mathematics, Pascal's triangle is a triangular array of the binomial coefficients.

Binomial coefficients can be read as "n choose k" - how many ways are there to choose k elements from a set of n elements?

The entries in each row are numbered with row n = 0 at the top, and the entries in each row are numbered from the left beginning with k = 0

The kth element in the nth row represents "n choose k"

img

Elements in each row of Pascal's triangle can be found by summing the two numbers in the row above and to the left and right of the element.

This property can be seen as a closed formula:

img

Let's try and create a recursive method that will find us "n choose k" using the above formula.

What are the base cases?

We know that there is only one way to choose zero elements from an n-element set, as well as _one_way to choose n elements from an n-element set.

// This function will return "n choose k"
public int pascal( int n, int k )
{
    if ( k == 0 || k == n )
        return 1;
    return pascal( n - 1, k - 1 ) + pascal( n - 1, k );
}

This function leaves us with the same problem we hads with the Fibonacci function: we are going to be recalculating subproblems that we have already solved before.

We can fix this like we did with the Fibonacci function: memorizing the value of the subproblems so that we don't have to recalculate them later.

int[][] dp = new int[ N_SIZE ][ K_SIZE ];
public int pascal( int n, int k )
{
    if ( k == 0 || k == n )
        return 1;
    if ( dp[ n ][ k ] != 0 )
        return dp[ n ][ k ];
    return dp[ n ][ k ] = pascal( n - 1, k - 1 ) + pascal ( n - 1, k );
}

Knapsack Problem

Problem Statement

You have a knapsack that can hold up to a certain weight W, and you have N items that you can pack for a trip; however, all of these items might not fit in your knapsack.

Each item you can pack has a weight w and a value v.

Your goal is to pack some items into your knapsack such that the total weight of all of the items doesn't exceed the maximum weight limit W, and the sum of all the values of the items in your knapsack is maximized.

Approaches

  1. Calculate all subsets of items and see which subset has the highest value, but also stays under the knapsack's weight limit
  2. Create some ratio for each item v / w and take the items with the highest ratio until you can't pack anymore
  3. Use dynamic programming

Solving Knapsack: Take I - Subset Solution

Let's calculate all subsets of the N items that we have.

This means that there are 2N possible subsets that we will need to go through.

However, if N is sufficiently large (larger than 25), this approach will be too slow

Solving Knapsack: Take II - Ratio Solution

Imagine we have a knapsack with W = 6 and are given the following set of items:
w = {2, 2, 2, 5}
v = {7, 7, 7, 20}

Let's find the v / w ratio of each item
v / W = {3.5, 3.5, 3.5, 4}

Now that we have the ratios, let's take the items with the greatest ratio until we have no more space left in the knapsack.

We will take the item with w = 5, v = 20 first and put it into oiur knapsack.

We now have 1 weight left in our knapsack, so we cannot fit any of the other items in our knapsack, so we end up with a value of 20.

However, if we would've taken the other three items, we would've had no weight left and a value of 21 instead.

Solving Knapsack: Take III - Dynamic Programming

There are two approaches to dynamic programming:

  • Top-down: define the overall problem first and what subproblems you will need to solve in order to get your answer
  • Bottom-up: start by solving subproblems and build up to the subproblems

We will look at how to solve the knapsack problem using both approaches

Bottom-Up Solution

Using the bottom-up approach, we need to first solve all of the possible subproblems, and then we can use those to solve our overall problem.

We will create a table that will hold the solutions to these subproblems, and keep building on it until we are done and have our answer.

Let's say we have a knapsack with capacity W = 6 and the following weights and values for N = 5 items: w = {3, 2, 1, 4, 5}
v = {25, 20, 15, 40, 50}

Let's figure out for all capacities, j, less than W = 6, what is the maximum value we can get if we only use the first i items

dp[ i ][ j ] will be the solution for each subproblem

Let's create our table; each cell will represent dp[ i ][ j ]

0 1 2 3 4 5 6
0
w = 3, v = 25 1
w = 2, v = 20 2
w = 1, v = 15 3
w = 4, v = 40 4
w = 5, v = 50 5

If we can't use any of the items (i = 0), the value at any capacity will be 0

0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
w = 3, v = 25 1
w = 2, v = 20 2
w = 1, v = 15 3
w = 4, v = 40 4
w = 5, v = 50 5

For i = 1, we can only take the first item in our set, so we want to take it whenever we have the capacity for it

0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
w = 3, v = 25 1 0 0 0 25 25 25 25
w = 2, v = 20 2
w = 1, v = 15 3
w = 4, v = 40 4
w = 5, v = 50 5

For i = 2, we can now take the second item in our set in addition to the first item, but only when taking the item at a given capacity will give us greater value than not taking it.

For example, at capacity j = 2, previously when we didn't have the item, we could get at most 0 value, but if we now take the item, we can get at most 20 value.

At capacity j = 3, previously when we didn't have the item, we could get at most 25 value, but if we now take the item, we can get 20 value AND the maximum value we could get previously at capacity j = 1, which is 0 (since we are looking at a capacity of j = 3, and we took the second item, the capacity we have left is j = 1, so we look at the maximum value we could get at this weight with all of the previous items). In this case, we do not want to take the item, because doing so will give us a lower value (20 < 25).

At capacity j = 5, previously when we didn't have the item, we could get at most 25 value, but if we now take the item, we can get 20 value AND the maximum value we could get previously at capacity j = 3, which is 25 (since we are looking at a capacity of j = 5, and we took the second item, the capacity we have left is j = 3, so we look at the maximum value we could get at this weight with all of the previous items). In this case, we do want to take the item, because doing so will give us more value (45 > 25).

0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
w = 3, v = 25 1 0 0 0 25 25 25 25
w = 2, v = 20 2 0 0 20 25 25 45 45
w = 1, v = 15 3
w = 4, v = 40 4
w = 5, v = 50 5

For i = 3, we repeat the same process that we did for i = 2.

0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
w = 3, v = 25 1 0 0 0 25 25 25 25
w = 2, v = 20 2 0 0 20 25 25 25 25
w = 1, v = 15 3 0 15 20 35 40 45 60
w = 4, v = 40 4
w = 5, v = 50 5

For i = 4, we repeat the same process as before

0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
w = 3, v = 25 1 0 0 0 25 25 25 25
w = 2, v = 20 2 0 0 20 25 25 45 45
w = 1, v = 15 3 0 15 20 35 40 45 60
w = 4, v = 40 4 0 15 20 35 40 55 60
w = 5, v = 50 5

For i = 5, we repeat the same process as before

0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
w = 3, v = 25 1 0 0 0 25 25 25 25
w = 2, v = 20 2 0 0 20 25 25 45 45
w = 1, v = 15 3 0 15 20 35 40 45 60
w = 4, v = 40 4 0 15 20 35 40 55 60
w = 5, v = 50 5 0 15 20 35 40 55 60

Now that the table is filled out, we can solve our original problem, where i = 5 and j = 6, by looking up the answer from the table

So our answer is: dp[ 5 ][ 6 ] = 60

for ( int i = 1; i <= N; i++ )
{
    for ( int j = 0; j <= W; j++)
    {
        if ( weight[ i ] <= j )
        {
            if ( value[ i ] + dp[ i - 1 ][ j - weight[ i ] ] > dp[ i - 1 ][ j ] )
            {
                dp[ i ][ j ] = value[ i ] + dp[ i - 1 ][ j - weight[ i ] ];
            }
            else
            {
                dp[ i ][ j ] = dp[ i - 1 ][ j ];
            }
        }
        else
        {
            dp[ i ][ j ] = dp[ i - 1][ j ];
        }
    }
}

Top-Down Solution

To solve the problem using the top-down approach, we will try to come up with some recursive function that will give us the answer.

As we did with the bottom-up approach, we will go item by item and see if we want to take it or not.

We will also keep track of how much weight we have left in the knapsack as we go through the items (this will help us determine if we can take an item or not).

Note: when we're looking at an item, we only have two options: take or ignore

This is why this problem is called the "0/1 Knapsack Problem"

public int solve( int i, int j )
{
    // Determines the max value you can get when starting at the ith item with j remaining weight left to use
}

Let's try and figure out some base cases for this function.

What happens if j == 0?

  • the max value we get by starting at any index with no weight left will be zero

What happens if i == N?

  • the max value we get by starting at an index outside of our item range will be zero

Let's look at every other case where i != N and j > 0

What happens if the weight of the ith item is greater than the remaining weight, j?

If the weight of the item we are currently looking at is greater than the amount of weight we have left, there's no way that we can take this item, so we ignore it

solve( i + 1, j )

The maximum value we get by starting at an index where we can't take the item will be determined by the maximum value we get by starting at the next item with the same remaining weight to use.

What happens if the weight of the ith item is less than or equal to the remaining weight, j?

Remember, we only have two options: take or ignore

We know what ignoring an item looks like:

solve( i + 1, j )

But what does taking an item look like?

Well, we know that the value of the remaining weight will be different

  • we took an item, so we need to subtract out it's weight from the remaining weight

We also know that since we took the item, we can add its value to our result

Our resulting function call for taking an item would be

value[ i ] + solve( i + 1, j - weight[ i ] )

The maximum value we get by starting at an index where we take the item can be determined by the sum of

  • the value of the item, and
  • the maximum value we get by starting at the next item with the new remaining weight

However, we just saw two separate function calls where we have enough weight to take an item, so which one do we use?

int ignore = solve( i + 1, j );
int take = value[ i ] + solve( i + 1, j - weight[ i ] );
Math.max( ignore, take );

We now know our solution handles every case for the Knapsack problem, giving us the optimal solution when we call solve( 0, W ), and it shows the problem has an optimal substructure - that is, an optimal solution can be constructed from the optimal solutions of its subproblems.

If we solve any subproblem solve( i, j ), we are guaranteed to get the optimal answer, and we can use these optimal subproblems to solve other subproblems.

We know that the problem has optimal substructure, but does it have any overlapping subproblems?

Let's look at an example:
v = {100, 70, 50, 10}
w = {10, 4, 6, 12}
W = 12

Imagine that we take the first item and ignore the next two

  • we will be at solve( i = 3, j = 2 )

Imagine that we ignore the first item and take the next two

  • we will be at solve( i = 3, j = 2 )

We have now determined we have overlapping subproblems, so we can save the value of a specific index / remaining weight pair, so we don't have to recompute the solution to the subproblem each time

int[][] dp = new int[ N ][ W ];
public int solve( int i, int j )
{
    // If there's no more space or we run out of items, we can't get anymore value
    if ( j == 0 || n == N )
        return 0;
    // If we have already solved this subproblem, return the value
    if ( dp[ i ][ j ] != 0 )
        return dp[ i ][ j ];
        
    // If the weight of the current item is greater than the weight we have left in the knapsack, ignore it
    if ( weight[ i ] > j )
        return solve( i + 1, j );
        
    // For every other case, determine if ignoring or taking the current item will yield more value
    int ignore = solve( i + 1, j );
    int take = value[ i ] + solve( i + 1, j - weight[ i ] );
    return dp[ i ][ j ] = Math.max( ignore, take );
}

Problems