`

A crack at Dynamic Programming

 
阅读更多

From: http://blog.rfaisal.com/2013/05/19/a-crack-at-dynamic-programming/

Dynamic Programming is a discrete optimization technique. It means, the variables we want to calculate using this method are discrete. As an example, if x is one such variable then x\in\{1,2,3,4\} is acceptable, but ‘x is a real number between 0 and 1′ is NOT acceptable since there are infinitely many real numbers between 0 and 1. In math terms, we can say that the domain of the variable x is a countable set.

Problems that are solved by dynamic programming are recursive nature. Let’s look at the problem that ask us to calculate the sum up to a number, i.e., if f_s is such a function then f_s(5)=0+1+2+3+4+5. The recursive definition (assuming i is non negative) is following:

f_{s}(i)=\begin{cases}0 & ,i=0\\i+f_{s}(i-1) & ,i\geq1\end{cases}

A recursive implementation will be following:

1
2
3
4
int sum(int i){
    if(i==0) return 0;
    else return i+sum(i-1);
}

A iterative implementation will be following:

1
2
3
4
5
int sum(int i){
    int ret=0;
    while(i>=0) ret+=i--;
    return ret;
}

As we can see both implementation has the same time complexity. Because, there is no overlapping sub-problem here!

Now, let’s look at another problem that ask us to calculate the i^{\text{th}} Fibonacci number. If f_f is such a function then the recursive definition (assuming i is non negative) is following:

f_{f}(i)=\begin{cases}0 & ,i=0\\1 & ,i=1\\f_{f}(i-1)+f_{f}(i-2) & ,i\geq2\end{cases}

A recursive implementation will be following:

1
2
3
4
5
int fibo(int i){
    if(i==0) return 0;
    else if (i==1) return 1;
    else return fibo(i-1)+fibo(i-2);
}

A iterative implementation will be following:

1
2
3
4
5
6
7
8
9
10
int fibo(int i){
    if(i==0) return 0;
    else if (i==1) return 1;
    int []table= new int[i+1];
    table[0]=0;
    table[1]=1;
    for(int j=2;j<=i;j++)
        table[j]=table[j-1]+table[j-2];
    return table[i];
}

Now, in this case, the iterative implementation is more efficient than the recursive implementation because there are overlapping sub-problems and the recursive solution requires solving the sub-problems more than once. For example, if we want to calculate ‘fibo(5)’, then the recursive implementation will call ‘fibo(4)’ and ‘fibo(3)’, in the next iteration ‘fibo(4)’ will call ‘fibo(3)’ and ‘fibo(2)’. So, ‘fibo(3)’ will be calculated twice from scratch. Whereas, in the iterative implementation the calculated value for a sub-problem is saved and can be used without recalculation. Obviously, the iterative implementation requires \mathcal{O}(n) more memory to save the results of the sub-problems. We have also just written our first dynamic programming solution for the Fibinacci problem.

Dynamic programming is an iterative implementation of a recursive problem with overlapping sub-problems that trades CPU cycles for memory.

Maximum Value Contiguous Subsequence (MVCS)

Let’s now take a look at a sightly harder problem. The MVCS is defined as follows:

Given a sequence, find the Contiguous Sub-sequence, sum of which is greater than that of any other Contiguous Sub-sequences. Recall, for \{1,2,3,4,5\}, \{1,4,5\} is a Sub-sequence but not a Contiguous Sub-sequence. If the input is \{-15, 29, -36, 3, -22, 11, 19, -5\} then MVCS is \{11, 19\} with the sum 30.

Note that this problem is only interesting if there are both positive and negative numbers in the sequence. If there are only positive numbers then the answer is the input array, and if there are only negative numbers then the answer is an empty set. For a sequence S_1,S_2,...,S_n, if f_{\text{mvcs}}(i)denote the sum of optimal sub-sequence ending at position i then it can be defined recursively as following:

f_{\text{mvcs}}(i)=\max_{}\left\{ f_{\text{mvcs}}(i-1)+S_{i},S_{i}\right\}

So, the sum of MVCS will be \max_{i}\left\{f_{\text{mvcs}}(i)\right\}, and starting from where max occurs we can now backtrack to get MVCS. The implementation is following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class MaxValueContiguousSubSeq {
    private int[] seq;
    /**
     * Needed for dynamic programming algorithm.
     */
    private int []table;
    private int max_i=0;
    private int max=0;
    private boolean isCalculated=false;
    public MaxValueContiguousSubSeq(int[] seq){
        this.seq=seq;
        if(seq!=null && seq.length!=0)
            table= new int[seq.length];
    }
    /**
     * Calculates the MVCS
     * @return sum of the MVCS
     */
    public int calculate(){
        isCalculated=true;
        if(seq==null || seq.length == 0)
            return max;
        table[0]=seq[0];
        max=Math.max(max, table[0]);
        for(int i=1;i<seq.length;i++){
            table[i]=Math.max(table[i-1]+seq[i], seq[i]);
            if(max<table[i]){
                max=table[i];
                max_i=i;
            }
        }
        return max;
    }
    public int[] getMaxValueContiguousSubSeq(){
        if(seq==null || seq.length == 0)
            return new int[0];
        if(!isCalculated) calculate();
        ArrayList<Integer> bt=backTrack(max_i,max);
        int []ret= new int[bt.size()];
        for(int i=0;i<bt.size();i++)
            ret[i]=bt.get(i);
        return ret;
    }
    private ArrayList<Integer> backTrack(int i,int sum){
        if(i<0 || sum<=0)
            return new ArrayList<Integer>();
        else{
            ArrayList<Integer> ret=backTrack(i-1,sum-seq[i]);
            ret.add(seq[i]);
            return ret;
        }
    }
}

Longest Increasing Sub-sequence (LIS)

The LIS is a similar type of problem as the MVCS.

Given a sequence, find the longest Sub-sequence (not necessarily Contiguous) such that each element is strictly greater than its previous in the sub-sequence. If the input is \{-2, 11, -4, 13,-3, -5, -1, 2\} then the LIS is \{-4,-3,-1,2\}.

For a sequence S_1,S_2,S_3,...,S_n, if f_{\text{lis}}(i) denote the length of longest increasing sub-sequence ending at position i then it can be defined recursively as following:

f_{\text{lis}}(i)=\max_{j<i,S_j<S_i}\left\{ f_{\text{lis}}(i-1)\right\}+1

So, the length of LIS will be \max_{i}\left\{f_{\text{lis}}(i)\right\}. Backtracking will be tricky, since f_{\text{lis}}(i) does not give enough information to track the previous element. That’s why for backtracking we need to use an extra array to save the path. The implementation is following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class LongestIncreasingSubSeq {
    private int[] seq;
    /**
     * Needed for backtracking. Since we are explicitly using this the table variable (look at other dp implementation) can be local in calculate function
     */
    private int []path;
    private int max_i=0;
    private int max=0;
    private boolean isCalculated=false;
    public LongestIncreasingSubSeq(int[] seq){
        this.seq=seq;
        if(seq!=null && seq.length!=0){
            path= new int[seq.length];
        }
    }
    public int[] getLongestIncreasingSubSeq(){
        if(seq==null || seq.length == 0)
            return new int[0];
        if(!isCalculated) calculate();
        ArrayList<Integer> bt=backTrack(max_i);
        int []ret= new int[bt.size()];
        for(int i=0;i<bt.size();i++)
            ret[i]=bt.get(i);
        return ret;
    }
    private ArrayList<Integer> backTrack(int i){
        if(i<0)
            return new ArrayList<Integer>();
        else{
            ArrayList<Integer> ret=backTrack(path[i]);
            ret.add(seq[i]);
            return ret;
        }
    }
    public int calculate(){
        isCalculated=true;
        if(seq==null || seq.length == 0)
            return 0;
        int []table= new int[seq.length];
        for(int i=0;i<seq.length;i++){
            int t_max=0;
            path[i]=-1;
            for(int j=0;j<i;j++){
                if(seq[j]<seq[i] && table[j]>t_max){
                    t_max=table[j];
                    path[i]=j;
                }
            }
            table[i]=t_max+1;
            if(table[i]>max){
                max=table[i];
                max_i=i;
            }
        }
        return max;
    }
}

Unbounded Knapsack Problem

Let’s now take a crack at the popular knapsack problem. The unbounded knapsack problem is defined as follows:

There is a knapsack of capacity C and there are there are n items with weights w_1, w_2, ..., w_nand values v_1, v_2, ..., v_n. Assume C,w_1, w_2, ..., w_n are strictly positive integers and there are infinitely many of each items, i.e., unbounded. Determine the number of each item to include in the knapsack so that the total weight is less than or equal to the knapsack capacity and the total value is maximized.

Let f_k(w) be the maximum value that can be attained with total weight less than or equal to w. Then f_k(w) can be defined recursively as follows:

f_{k}(w)=\begin{cases}0 & ,w=0\\\max_{w_{i}\leq w}\left(f_{k}(w-c_{i})+v_{i}\right) &,w\geq1\end{cases}

The implementation of this problem with the recursive formula is now trivial, but backtracking is very tricky. For backtracking, you will need at least 2C+2 more space, which is implemented here. There is a easier backtracking with \mathcal{O}(nC) extra space that can be found elsewhere.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class UnboundedKnapsack {
    private int[] weights;
    private int[] values;
    private int capacity;
    /**
     * Needed for backtracking.
     */
    private int []pathWeight;
    private int []pathIndex;
    private int []table;
    private boolean isCalculated=false;
    public UnboundedKnapsack(int capacity, int[] weights, int[] values) throws Exception{
        if(isNullOrEmpty(weights) || isNullOrEmpty(values) || weights.length!=values.length)
            throw new Exception("Wrong input.");
        this.capacity=capacity;
        this.weights=weights;
        this.values=values;
        pathWeight= new int[capacity+1];
        pathIndex= new int[capacity+1];
        table= new int[capacity+1];
    }
    private boolean isNullOrEmpty(int[] arr){
        return arr==null || arr.length==0;
    }
    public int[] getItems(){
        if(capacity==0)
            return new int[0];
        if(!isCalculated) calculate();
        ArrayList<Integer> bt=backTrack(capacity);
        int []ret= new int[weights.length];
        for(int i=0;i<bt.size();i++)
            ret[bt.get(i)]++;
        return ret;
    }
    private ArrayList<Integer> backTrack(int i){
        if(pathWeight[i]<0)
            return new ArrayList<Integer>();
        else{
            ArrayList<Integer> ret=backTrack(pathWeight[i]);
            ret.add(pathIndex[i]);
            return ret;
        }
    }
    public int calculate(){
        isCalculated=true;
        if(capacity==0)
            return 0;
        table[0]=0;
        pathWeight[0]=-1;
        for(int i=1;i<=capacity;i++){
            int max=-Integer.MAX_VALUE;
            pathWeight[i]=-1;
            for(int j=0;j<weights.length;j++){
                if(weights[j]<=i && table[i-weights[j]]+values[j]>max){
                    max=table[i-weights[j]]+values[j];
                    pathWeight[i]=i-weights[j];
                    pathIndex[i]=j;
                }
            }
            table[i]=max;
        }
        return table[capacity];
    }
}

Making Change Problem

The making change problem gives the optimal changes for a given amount of money.

Given n types of coin denominations of values c_1 < c_2 < ... < c_n (all integers). Assume c_1 = 1, so it is always possible to make change for any amount of money C. Give an algorithm which makes change for an amount of money C with as few coins as possible.

As we can see that this problem is almost identical to the unbounded knapsack problem except v_1, v_2, ...,v_n are all equal, i.e., choosing any of the coins gives us the same benefit and this is a minimization problem. So, if we set v_1=v_2=, ...,=v_n=-1 then it becomes identical to the unbounded knapsack problem, since -1 makes the maximization problem to a minimization problem. So, the implementation is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class MakingChange extends UnboundedKnapsack {
    public MakingChange(int money, int[] changes) throws Exception {
        super(money, changes, generateValuesforKnapSack(changes));
    }
    public static int[] generateValuesforKnapSack(int[] weights){
        if(weights==null || weights.length==0)
            return new int[0];
        int []ret= new int[weights.length];
        for(int i=0;i<weights.length;i++)
            ret[i]=-1;
        return ret;
    }
}

Edit Distance

Given two strings A=A_1A_2...A_n and B=B_1B_2...B_m, we want to transform A into B with a minimum number of operations of the following types: delete a character from A, insert a character into A, or change some character in A into a new character. The minimal number of such operations required to transform A into B is called the edit distance between A and B.

To calculate the edit distance, we will define f_d(i,j) to be the minimum distance to transform the 1sti characters of string A, i.e., A_1A_2...A_i to the 1st j characters of string B, i.e., B_1B_2...B_j, and the cost for insertion, deletion and substitution be respectively c_i, c_d, c_s. Then the recursive definition is:

f_{ed}(i,j)=\begin{cases}0 & ,i=0\mbox{ or }j=0\\\min\begin{cases}f_{ed}(i-1,j)+c_{d}\\f_{ed}(i,j-1)+c_{i}\\\begin{cases}f_{ed}(i-1,j-1) & ,A_{i}=B_{j}\\f_{ed}(i-1,j-1)+c_{s} & ,A_{i}\neq B_{j}\end{cases}\end{cases} & ,i\neq0\mbox{ and }j\neq0\end{cases}

With this recursive definition the implementation is following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class EditDistance {
    /**
     * Costs.
     */
    private static final int c_i=1;
    private static final int c_d=1;
    private static final int c_s=1;
    private String s1;
    private String s2;
    /**
     * Needed for dynamic programming algorithm.
     */
    private int [][]table;
    private int getMin(int a,int b,int c){
        int min=a;
        if(min>b) min=b;
        if(min>c) min=c;
        return min;
    }
    private boolean emptyOrNull(String s){
        return s==null || s.equals("");
    }
    public EditDistance(String s1,String s2){
        this.s1=s1;
        this.s2=s2;
        if(!(emptyOrNull(s1) || emptyOrNull(s2) || s1.equals(s2))) //cases we know the edit distance
            table= new int[s1.length()+1][s2.length()+1]; // a dummy 1st column and dummy 1st row
    }
 
    /**
     * Calculate the edit distance between s1 and s2 by dynamic programming.
     * @return edit distance
     */
    public int calculate(){
        if(emptyOrNull(s1) && emptyOrNull(s2)) return 0;
        else if(emptyOrNull(s1)) return s2.length();
        else if(emptyOrNull(s2)) return s1.length();
        else if(s1.equals(s2)) return 0;
         
        for(int i=0;i<s1.length()+1;i++){
            table[i][0]=i;
        }
        for(int j=0;j<s2.length()+1;j++){
            table[0][j]=j;
        }
        for(int i=1;i<s1.length()+1;i++){
            for(int j=1;j<s2.length()+1;j++){
                int dis=s1.charAt(i-1)==s2.charAt(j-1)?0:c_s;
                table[i][j]=getMin(c_d+table[i-1][j], //deletion
                        c_i+table[i][j-1], //insertion
                        dis+table[i-1][j-1]); //substitution
            }
        }
        return table[s1.length()-1][s2.length()-1];
    }
}

[Source code: link]
[Unit tests: link]
[Additional practice problems: link]

 

分享到：
| DropBox Interview - Same file in a direc ...
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics