动态规划

1、求最长公共子序列

void LCS(char s1[], char s2[], int l1, int l2)
{
    int c[Max + 1][Max + 1];
    int i, j;
    int m;
    for (i = 0; i < l1; i++)
    for (j = 0; j < l2; j++)
        c[i][j] = 0;
    for (i = 1; i <= l1; i++)
    for (j = 1; j <= l2; j++) {
        if (s1[i - 1] == s2[j - 1])
        c[i][j] = c[i - 1][j - 1] + 1;
        else {
        c[i][j] =
            c[i - 1][j] > c[i][j - 1] ? c[i - 1][j] : c[i][j - 1];
        }
    }
    m = c[l1][l2];
    printf("LCS:%d\n", m);
    i = l1;
    j = l2;
    while (m) {
    if (c[i][j] == c[i - 1][j - 1]+1) {
        printf("%c\t", s1[i - 1]);
        i--;
        j--;
        m--;
    } else if (c[i][j] == c[i - 1][j])
        i--;
    else if (c[i][j] == c[i][j - 1])
        j--;
    }
}

2、求最长公共子串

sadas

3、0-1背包问题

#include<stdio.h>
#include<iostream>
using namespace std;
void max_value(int weight[],int value[],int num,int capacity)
{
  int i,j;
  int c[100][100];
  for(i=0;i<=num;i++)
       c[i][0]=0;
  for(i=0;i<=capacity;i++)
       c[0][i]=0;
  for(i=1;i<=num;i++)
    for(j=1;j<=capacity;j++)
   {
      if(weight[i]>j)
          c[i][j]=c[i-1][j];
     else{
           c[i][j]=(c[i-1][j-weight[i]]+value[i])>c[i-1][j]?(c[i-1][j-weight[i]]+value[i]):c[i-1][j];
          }
  } 
  cout<<"maxvalue:"<<c[num][capacity];
j=capacity;
cout<<endl;
for(i=num;i>=1;i--)
{
   if(c[i][j]>c[i-1][j])
   {
     cout<<i<<' ';
     j=j-weight[i];
   }
}
}
int main()
{
 int i;
 int num,capacity;
 int * weight;
 int * value;
 cin>>capacity>>num;
 weight=new int[num+1];
 value=new int[num+1];
 weight[0]=value[0]=0;
 for(i=1;i<=num;i++){
   cin>>weight[i]>>value[i];
}
 max_value(weight,value,num,capacity);
 
 return 0;
}

4、最短编辑距离

#include<iostream>
#include<string>
using namespace std;
int min(int a, int b)
{
    return a<b ? a : b;
}

void shortest_edit_distance(string s1, string s2, int l1, int l2)
{
    int i, j;
    int temp;
    int d;
    int **c = new int*[l1 + 1];
    for (i = 0; i < l1 + 1; i++)
    c[i] = new int[l2 + 1];
    for (i = 0; i < l1 + 1; i++)
    c[i][0] = i;
    for (i = 0; i < l2 + 1; i++)
    c[0][i] = i;
    for (i = 1; i < l1 + 1; i++)
    for (j = 1; j < l2 + 1; j++) {
        temp = min(c[i][j - 1] + 1, c[i - 1][j] + 1);
        d = 1;
        if (s1[i-1] == s2[j-1])
        d = 0;
        temp = min(temp, c[i - 1][j - 1] + d);
        c[i][j] = temp;
    }
    cout << "Dis:" << c[l1][l2] << endl;
    for (i = 0; i < l1 + 1; i++) {
    delete[]c[i];
    c[i] = NULL;
    }
    delete[]c;
    c = NULL;

}

int main()
{
    string s1 = "sailn";
    string s2 = "failing";
    int l1;
    int l2;
    l1 = s1.size();
    l2 = s2.size();
    shortest_edit_distance(s1, s2, l1, l2);
}