通过LeetCode上【70. 爬楼梯】学习
class Solution { public: int climbStairs(int n) { if(n == 1) return 1; if(n == 2) return 2; return climbStairs(n - 1) + climbStairs(n - 2); } };利用回溯算法求解八皇后问题
#include"stdio.h" #include"stdlib.h" #include"assert.h" #define MAX 30 int check_pos(const int r[MAX],const int i,const int j); void print(const int r[MAX],const int n); int queen_place(int r[MAX],const int n); int main(int argc,char *argv[]){ if(argc!=2){ fprintf(stderr,"Please input the number of queen!\n"); return 0; } int n=atoi(argv[1]); if(n<4){ fprintf(stderr,"The number of queen must be larger than 4 !\n"); return 0; } int results[MAX]; // results[i]=j，表示把第i个皇后放在位置(i,j)上 int num = queen_place(results,n); return 0; } int queen_place(int r[MAX],const int n){ int i,j,num; i=0;j=0,num=0; while(1){ int find=0; while(j<n){ // 寻找第i个皇后放置的位置j if(check_pos(r,i,j)) break; j++; } if(j<n){ // 如果找到了记录该位置，继续放置第i个皇后 r[i++] = j; j = 0; }else{ // 如果没有找到合适的位置，回溯到第i-1个皇后，将其位置放在原来位置的下一个位置 j = r[--i] + 1 ; } if(i == n && r[i-1]<n){ //找到了一个合适的解 //print(r,n); j=r[--i]+1; //继续寻找其他解 num++; }else if(i<0) //已经找到了全部的解 break; } printf("num:%d\n",num); return num; } //第i个皇后放在(i,j)位置是否合适 int check_pos(const int r[MAX],const int i,const int j){ int k; for(k=0;k<i;k++){ if(r[k] == j) //是否在同列 return 0; if(r[k]+k == i+j) //是否在45度对角线 return 0; if(r[k]-k == j-i) //是否在135度对角线 return 0; } return 1; } //打印皇后放置的位置 void print(const int r[MAX],const int n){ int i,j; for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(r[i]==j) printf("1 "); else printf("0 "); } printf("\n"); } printf("----------------------------\n"); }利用回溯算法求解 0-1 背包问题
#include <iostream> #include <stdio.h> //#include <conio.h> using namespace std; int n;//物品数量 double c;//背包容量 double v[100];//各个物品的价值 value double w[100];//各个物品的重量 weight double cw = 0.0;//当前背包重量 current weight double cp = 0.0;//当前背包中物品总价值 current value double bestp = 0.0;//当前最优价值best price double perp[100];//单位物品价值(排序后) per price int order[100];//物品编号 int put[100];//设置是否装入，为1的时候表示选择该组数据装入，为0的表示不选择该组数据 //按单位价值排序 void knapsack() { int i,j; int temporder = 0; double temp = 0.0; for(i=1;i<=n;i++) perp[i]=v[i]/w[i]; //计算单位价值（单位重量的物品价值） for(i=1;i<=n-1;i++) { for(j=i+1;j<=n;j++) if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[] { temp = perp[i]; //冒泡对perp[]排序 perp[i]=perp[i]; perp[j]=temp; temporder=order[i];//冒泡对order[]排序 order[i]=order[j]; order[j]=temporder; temp = v[i];//冒泡对v[]排序 v[i]=v[j]; v[j]=temp; temp=w[i];//冒泡对w[]排序 w[i]=w[j]; w[j]=temp; } } } //回溯函数 void backtrack(int i) { //i用来指示到达的层数（第几步，从0开始），同时也指示当前选择玩了几个物品 double bound(int i); if(i>n) //递归结束的判定条件 { bestp = cp; return; } //如若左子节点可行，则直接搜索左子树; //对于右子树，先计算上界函数，以判断是否将其减去 if(cw+w[i]<=c)//将物品i放入背包,搜索左子树 { cw+=w[i];//同步更新当前背包的重量 cp+=v[i];//同步更新当前背包的总价值 put[i]=1; backtrack(i+1);//深度搜索进入下一层 cw-=w[i];//回溯复原 cp-=v[i];//回溯复原 } if(bound(i+1)>bestp)//如若符合条件则搜索右子树 backtrack(i+1); } //计算上界函数，功能为剪枝 double bound(int i) { //判断当前背包的总价值cp＋剩余容量可容纳的最大价值<=当前最优价值 double leftw= c-cw;//剩余背包容量 double b = cp;//记录当前背包的总价值cp,最后求上界 //以物品单位重量价值递减次序装入物品 while(i<=n && w[i]<=leftw) { leftw-=w[i]; b+=v[i]; i++; } //装满背包 if(i<=n) b+=v[i]/w[i]*leftw; return b;//返回计算出的上界 } int main() { int i; printf("请输入物品的数量和背包的容量："); scanf("%d %lf",&n,&c); /*printf("请输入物品的重量和价值：\n"); for(i=1;i<=n;i++) { printf("第%d个物品的重量：",i); scanf("%lf",&w[i]); printf("第%d个物品的价值是：",i); scanf("%lf",&v[i]); order[i]=i; }*/ printf("请依次输入%d个物品的重量:\n",n); for(i=1;i<=n;i++){ scanf("%lf",&w[i]); order[i]=i; } printf("请依次输入%d个物品的价值:\n",n); for(i=1;i<=n;i++){ scanf("%lf",&v[i]); } knapsack(); backtrack(1); printf("最优价值为：%lf\n",bestp); printf("需要装入的物品编号是："); for(i=1;i<=n;i++) { if(put[i]==1) printf("%d ",order[i]); } return 0; }利用分治算法求一组数据的逆序对个数
#include<iostream> #include<fstream> using namespace std; int reversePair(int arr[], int temp[], int left, int right); int merge(int arr[], int temp[], int left, int mid, int right); int main(void) { fstream f("test.txt", fstream::in | fstream::out); int test[100]; int t[100];//临时数组用于合并步骤，不在递归函数中开启数组，防止递归过程内存中同时存在大量数组 int temp; int i = 0; while(f >> temp) { test[i] = temp; i++; } cout << reversePair(test, t, 0, i - 1) << endl; f.close(); return 0; } int reversePair(int arr[], int temp[], int l, int r) { if(l == r) return 0; int m = (l + r) / 2; int ln = reversePair(arr, temp, l, m);//左序列逆序对数量 int rn = reversePair(arr, temp, m + 1, r);//右序列逆序对数量 int mn = merge(arr, temp, l, m, r);//左序列与右序列元素构成的逆序对数量 return ln + rn + mn; } int merge(int arr[], int temp[], int l, int m, int r) { int count = 0, i, j; for(i = l; i <= r; i++) temp[i] = arr[i]; int k = l; for(i = l, j = m + 1; i <= m && j <= r;k++) { if(temp[i] > temp[j]) { count += m - i + 1;//每次发现左序列元素比右序列元素大，逆序对数量增加，m-i+1即为该元素到左序列尾的元素数量 //其余代码为归并排序的步骤 arr[k] = temp[j]; j++; } else { arr[k] = temp[i]; i++; } } if(i > m) { while(j <= r) { arr[k] = temp[j]; j++; k++; } } else { while(i <= m) { arr[k] = temp[i]; i++; k++; } } return count; }0-1 背包问题
#include <iostream> using namespace std; #define max(a,b) (((a) > (b)) ? (a) : (b)) int w[]={0,3,6,3,8,6};//商品重量 int v[]={0,4,6,6,12,10};//商品价值 int W = 10; //背包容量 int c[6][11]={0};//c[i][j]表示在商品1到i中，背包容量为j时，最大价值 void Package0_1(int w[],int v[],int W,int n,int c[][11])// { for(int i=1;i<=n;i++) //逐行填表c[i][j] { for (int j=1;j<=W;j++) { if ( i == 1) //填写第1行时，不参考其他行 { if (j < w[i]) c[i][j]=0; else c[i][j] = v[i]; } else { if ( j < w[i]) //背包容量小于商品i的重量，商品i一定不选 { c[i][j] = c[i-1][j]; } else { c[i][j] = max(c[i-1][j],v[i]+c[i-1][j-w[i]]);//比较选与不选商品i的背包总价值大小 } } } } for(int m =1;m<6;m++) { for (int n=0;n<11;n++) { cout<<c[m][n]<<" "; } cout<<endl; } } void Print_Package0_1(int c[][11]) //构造解 { int i=5; int j=10; cout<<"总价值为"<<c[i][j]<<endl; while(i!=1) { if ( c[i][j] == c[i-1][j] ) { cout<<"商品"<<i<<"不选"<<endl; } else { cout<<"商品"<<i<<"选"<<endl; j = j - w[i]; } i--; } if ( c[i][j] == 0) // { cout<<"商品"<<i<<"不选"<<endl; } else { cout<<"商品"<<i<<"选"<<endl; } } int main() { Package0_1(w,v,W,5,c); Print_Package0_1(c); return 0; }最小路径和（详细可看 Minimum Path Sum）
int minPathSum(vector<vector<int>>& grid) { int m=(int)grid.size(); int n=(int)grid[0].size(); vector<vector<int>> dp(m,vector<int>(n,0)); dp[0][0]=grid[0][0]; for(int i=1;i<m;i++) dp[i][0]=dp[i-1][0]+grid[i][0]; for(int i=1;i<n;i++) dp[0][i]=dp[0][i-1]+grid[0][i]; for(int i=1;i<m;i++) for(int j=1;j<n;j++) dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]; return dp[m-1][n-1]; }编程实现莱文斯坦最短编辑距离
#include<bits/stdc++.h> using namespace std; int min(int a,int b,int c) { return (a<b)?(a<c?a:c):(b<c?b:c); } int main() { FILE * file; freopen("input.txt", "r", stdin); freopen("output.txt","w",stdout); int d[6][8]; string a,b; cin>>a>>b; for (int i=0;i<=b.size()+1;i++) { for (int j=0; j<=a.size()+1;j++) { if (i==0&&j==0) d[i][j]=0; else if (i==0&& j > 0) d[i][j]=j; else if (i>0&&j==0) d[i][j]=i; else if(i>=1&&j>=1) { int k =((b[i-1]==a[j-1])?0:1); d[i][j]=min(d[i-1][j]+1, d[i][j-1]+1,d[i-1][j-1]+k); } } } /* for(int i=0;i<b.size()+1;i++) { for(int j=0;j<a.size()+1;j++) { cout<<d[i][j]+" "; } cout<<endl; } */ cout<<d[b.size()+1][a.size()+1]; return 0; }编程实现查找两个字符串的最长公共子序列
#include <stdio.h> #include <string.h> #define MAXLEN 50 void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN]) { int i, j; for(i = 0; i <= m; i++) c[i][0] = 0; for(j = 1; j <= n; j++) c[0][j] = 0; for(i = 1; i<= m; i++) { for(j = 1; j <= n; j++) { if(x[i-1] == y[j-1]) { c[i][j] = c[i-1][j-1] + 1; b[i][j] = 1; //如果使用'↖'、'↑'、'←'字符，会有警告，也能正确执行。 } //本算法采用1,3,2三个整形作为标记 else if(c[i-1][j] >= c[i][j-1]) { c[i][j] = c[i-1][j]; b[i][j] = 3; } else { c[i][j] = c[i][j-1]; b[i][j] = 2; } } } } void PrintLCS(int b[][MAXLEN], char *x, int i, int j) { if(i == 0 || j == 0) return; if(b[i][j] == 1) { PrintLCS(b, x, i-1, j-1); printf("%c ", x[i-1]); } else if(b[i][j] == 3) PrintLCS(b, x, i-1, j); else PrintLCS(b, x, i, j-1); } int main() { char x[MAXLEN] = {"ABCBDAB"}; char y[MAXLEN] = {"BDCABA"}; int b[MAXLEN][MAXLEN]; //传递二维数组必须知道列数，所以使用MAXLEN这个确定的数 int c[MAXLEN][MAXLEN]; int m, n; m = strlen(x); n = strlen(y); LCSLength(x, y, m, n, c, b); PrintLCS(b, x, m, n); return 0; }编程实现一个数据序列的最长递增子序列
#include <iostream> using namespace std; int lis(int A[], int n){ int *d = new int[n]; int len = 1; for(int i=0; i<n; ++i){ d[i] = 1; for(int j=0; j<i; ++j) if(A[j]<=A[i] && d[j]+1>d[i]) d[i] = d[j] + 1; if(d[i]>len) len = d[i]; } delete[] d; return len; } int main(){ int A[] = { 5, 3, 4, 8, 6, 7 }; cout<<lis(A, 6)<<endl; return 0; }