Dynamic Programming

There are three steps involved in solving a problem by dynamic programming:

  1. Formulate the answer as a recurrence relation or recursive algorithm.
  2. Show that the number of different parameter values taken on by your recurrence bounded by a (hopefully small) polynomial.
  3. Specify an order of evaluation for the recurrence so the partial results you need are always available when you need them.

longest increasing sequence

longest increasing sequence

partition problem

partition problem

traveler problem

traveler problem

problem 1

Given a set {1,2,3,4,5,6,7,8,9,10}, write an algorithm that prints out all the n digits or lesser combinations that can arise out of the set.

condition: Successive numbers need to be avoided.

Eg; if set = {1,2,3,4,5,6,7,8,9,10}
and n = 3

It should print

(1,3,5) —> no successive numbers
(1,4,6)
(1,5,7}
(1,6,8}
(1,7,9}
{1,8,10}
(1,9)
(1,10)
.
.
(10, 1, 3)
(10, 2, 4)
so on so forth.

Here is the code.
Given: "1234" and N = 2
It would print out "13", "14", "24"
 
all other strings ("43","41"..) are just permutation of the above result.
Working code. Just copy and paste it to your favorite IDE then compile away.
 
#include <iostream>
#include <string>
void printComb(const char ar[], bool used[], int SIZE){
       string str = "";
       for (int i = 0; i < SIZE; ++i){
               if (used[i]){
                       str += ar[i];
               }
       }
       cout << str <<  endl;
}
 
//variable u keeps track of the number of
//characters in our result
 
void comb(const char ar[], bool used[], int index, int u, int N,  int SIZE){
       if (u == N){
               printComb(ar, used, SIZE);
       } else if (index >= SIZE){
               return;
       } else {
               used[index] = true;
               ++u;
               comb(ar, used, index + 2, u, N, SIZE);
               used[index] = false;
               --u;
               comb(ar, used, index + 1, u, N, SIZE);
       }
}
 
int main(){
       int N = 2;
       string str  = "1234";
       bool used[str.length()];
       for (int i = 0; i < str.length(); ++i){
               used[i] = false;
       }
       comb(str.c_str(), used, 0, 0, N, str.length());
}

problem 2 : subset of strings

Given a character array, print all the subsets of those characters

Ouput: x1…xn where xi denotes whether the i-th element of the input appears in the subset or not

#include <stdio.h>
#include <stdlib.h>
 
void gen(int* input, int n, int index);
 
int main(int argc, char* argv[])
{
   int *input;
   int n;
 
   if (argc != 2) {
        printf("Usage: %s <#elements>\n",argv[0]);
        exit(0);
   }
 
   n = atoi(argv[1]);
 
   input = malloc(sizeof(int)*n);
   gen(input,n,0);
}
 
void gen(int* input, int n, int index)
{
    int i;
 
    if (index == n) {
        for (i = 0; i < n; i++)
            printf("%d",input[i]);
        printf("\n");
       return;
    }
 
   input[index] = 0;
   gen(input,n,index+1);
   input[index] = 1;
   gen(input,n,index+1);
}

problems

http://people.csail.mit.edu/bdean/6.046/dp/
http://www.gabormelli.com/RKB/Algorithm_Strategy
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License