1、三角数塔问题

设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示： 要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。【代码】//// 例题1 三角数字塔问题 ////#include <stdio.h>#include <stdlib.h>#define MAXN 101int n,d[MAXN][MAXN];int a[MAXN][MAXN];void fnRecursive(int,int);//递推方法函数声明int fnMemorySearch(int,int);//记忆化搜索函数声明int main(){ int i,j; printf("输入三角形的行数n(n=1-100):\n"); scanf("%d",&n); printf("按行输入数字三角形上的数(1-100):\n"); for(i=1; i<=n; i++) for(j=1; j<=i; j++) scanf("%d",&a[i][j]); for(i=1; i<=n; i++) for(j=1; j<=i; j++) d[i][j]=-1;//初始化指标数组 printf("递推方法：1\n记忆化搜索方法：2\n"); int select; scanf("%d",&select); if(select==1) { fnRecursive(i,j);//调用递推方法 printf("\n%d\n",d[1][1]); } if(select==2) { printf("\n%d\n",fnMemorySearch(1,1));//调用记忆化搜索方法 } else printf("输入错误！"); return 0;}void fnRecursive(int i,int j)//递推方法实现过程{ for(j=1; j<=n; j++) d[n][j]=a[n][j]; for(i=n-1; i>=1; i--) for(j=1; j<=i; j++) d[i][j]=a[i][j]+(d[i+1][j]>d[i+1][j+1]?d[i+1][j]:d[i+1][j+1]);}int fnMemorySearch(int i,int j)//记忆化搜索实现过程{ if(d[i][j]>=0) return d[i][j]; if(i==n) return(d[i][j]=a[i][j]); if(fnMemorySearch(i+1,j)>fnMemorySearch(i+1,j+1)) return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j))); else return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j+1)));}2、硬币问题问题描述：有n种硬币，面值分别为V1,V2,…,Vn, 每种有无限多。给定非负整数S，可以选用多少硬币，使得面值之和恰好为S，输出硬币数目的最小值和最大值。（1<=n<=100,0<=S<=10000,1<=Vi<=S）【代码】//// 例题1 硬币问题 ////#include <stdio.h>#include <stdlib.h>#define INF 100000000#define MAXNUM 10000#define MONEYKIND 100int n,S;int V[MONEYKIND];int min[MAXNUM],max[MAXNUM];void dp(int*,int*);//递推方法函数声明void print_ans(int*,int);//输出函数声明int main(){ int i; printf("输入硬币的种数n(1-100):\n"); scanf("%d",&n); printf("输入要组合的钱数S(0-10000):\n"); scanf("%d",&S); printf("输入硬币种类：\n"); for(i=1; i<=n; i++) { scanf("%d",&V[i]); } dp(min,max); printf("最小组合方案：\n"); print_ans(min,S); printf("\n"); printf("最大组合方案：\n"); print_ans(max,S); return 0;}void dp(int *min,int *max)//递推过程实现{ int i,j; min[0] = max[0] = 0; for(i=1; i<=S; i++)//初始化数组 { min[i]=INF; max[i]=-INF; } for(i=1; i<=S; i++) for(j=1; j<=n; j++) if(i>=V[j]) { if(min[i-V[j]]+1<min[i]){ min[i]=min[i-V[j]]+1;//最小组合过程 //printf("%d\n",min[i]); } if(max[i-V[j]]+1>max[i]) max[i]=max[i-V[j]]+1;//最大组合过程 }}void print_ans(int *d,int S)//输出函数实现{ int i; for(i=1; i<=n; i++) if(S>=V[i]&&d[S]==d[S-V[i]]+1) { printf("%d-",V[i]); print_ans(d,S-V[i]); break; }}3、矩形嵌套问题问题描述：有n个矩形，每个矩形可以用两个整数a,b描述，表示它的长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中，当且仅当a<c,b<d或者b<c,a<d（相当于把矩形X旋转90度）。例如(1,5)可以嵌套在(6,2)内，但不能嵌套在(3,4)内。你的任务是选出尽量多的矩形排成一行，使得除了最后一个之外，每一个矩形都可以嵌套在下一个矩形内。【代码】//// 例题2 矩形嵌套问题 ////#include <stdio.h>#include <stdlib.h>#define MAXNUM 100//矩形的最大个数struct Rect{ int x; int y;};int n;//矩形个数struct Rect rect[MAXNUM];int G[MAXNUM][MAXNUM];//邻接有向图int d[MAXNUM];//过程数组int dp(int i,int G[MAXNUM][MAXNUM]);int main(){ int i,j,z; printf("输入矩形个数n(1-100):\n"); scanf("%d",&n); printf("输入矩形的长和宽：\n"); for(i=1; i<=n; i++) { scanf("%d",&rect[i].x); scanf("%d",&rect[i].y); } for(i=1; i<=n; i++) for(j=1; j<=n; j++) { if(rect[i].x<rect[j].x&&rect[i].y<rect[j].y) G[i][j]=1; } printf("输入要开始的矩形z：\n"); scanf("%d",&z); //printf("%d-",z); int temp = dp(z,G); printf("最大可嵌套个数：%d\n",temp); return 0;}int dp(int i,int G[MAXNUM][MAXNUM]){ int j; if(d[i]>0) return d[i]; d[i]=1; for(j=1; j<=n; j++) if(G[i][j]) if(dp(j,G)+1>d[i]) { d[i]=dp(j,G)+1; } return d[i];}4、求一组数列的最长的不下降序列。问题描述：设有一个正整数序列b1，b2，b3，……，bn，若下标为i1<i2<i3，……<ik且有bi1≤bi2≤……bik则称存在一个长度为k的不下降序列。可能有多个不下降序列，输出最长序列的长度。 样例输入：13　7　9　16　38　24　37　18　样例输出：5 (7 9 16 24 37)【代码】//// 例题2 数组的最长不下降序列问题 ////#include <stdio.h>#include <stdlib.h>#define MAXNUM 100//最大数字个数int b[MAXNUM][2];int n;int len;int main(){ int i,j; printf("输入数列中数字的个数n(1-100)：\n"); scanf("%d",&n); printf("输入数字：\n"); for(i=1; i<=n; i++) { scanf("%d",&b[i][0]); b[i][1]=1; } for(i=2; i<=n; i++) { len = 0; for(j=1; j<i; j++) if((b[i][0]>=b[j][0])&&(b[j][1]>len)) len=b[j][1]; if(len>0) b[i][1]=len+1; } len = 1; for(j=2; j<=n; j++) if(b[j][1]>len) len = b[j][1]; printf("最长为：%d\n",len); return 0;}5、0-1背包问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?【代码】//// 0-1背包问题 ////#include <stdio.h>#include <stdlib.h>#define MAXN 100//物品种类最大数量int w[MAXN],V[MAXN];int C;//最大容量int n;//物品种类int d[MAXN][MAXN];int jMax;int min(int,int);//两数之间的最小值int max(int,int);//两数之间的最大值void print_ans(int d[][MAXN],int,int);//构造最优解并输出int main(){ int i,j; printf("输入物品种类数n(1-100):\n"); scanf("%d",&n); printf("输入每个种类的重量：\n"); for(i=1; i<=n; i++) { scanf("%d",&w[i]); } printf("输入每个种类的价值：\n"); for(i=1; i<=n; i++) { scanf("%d",&V[i]); } printf("输入背包的容量C：\n"); scanf("%d",&C); jMax=min(C,w[n]-1); for(j=0; j<=jMax; j++)