实验六 动态规划算法（4学时）
一、实验目的与要求
1、熟悉最长公共子序列问题的算法； 2、初步掌握动态规划算法； 二、实验题
若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
三、实验提示 include \#include \
void LCSLength(char *x ,char *y,int m,int n, int **c, int **b) {
int i ,j;
for (i = 1; i <= m; i++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) {
if (x[i]==y[j]) {
c[i][j]=c[i-1][j-1]+1; b[i][j]=1; }
else if (c[i-1][j]>=c[i][j-1]) {
c[i][j]=c[i-1][j]; b[i][j]=2; } else
{ c[i][j]=c[i][j-1]; b[i][j]=3; } } }
void LCS(int i ,int j, char *x ,int **b) {
if (i ==0 || j==0) return; if (b[i][j]== 1) {
LCS(i-1,j-1,x,b); printf(\ }
else if (b[i][j]== 2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); }
实验七 动态规划算法（4学时）
一、实验目的与要求
1、熟悉最长最大字段和问题的算法； 2、进一步掌握动态规划算法； 二、实验题
若给定n个整数组成的序列a1，a2，a3，……an，求该序列形如ai＋ai＋1＋……＋an的最大值。
三、实验提示
int MaxSum(int n,int *a,int &besti,int &bestj) {
intsum=0;
for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) {
int thissum=0;
for(int K=i;k<=j;k++)thissum+=a[k]; if(thissum>sum) {
sum=thissum; besti=i; bestj=j; } }
return sum; }
int MaxSum(int n,int *a,int &besti,int &bestj) {
intsum=0;
for(int i=1;i<=n;i++) {
int thissum=0;
for(intj=i;j<=n;j++) {
thissum+=a[j]; if(thissum>sum) {
sum=thissum; besti=i; bestj=j; } } }
return sum; }
实验八 回溯算法（4学时）
一、实验目的与要求
1、掌握装载问题的回溯算法； 2、初步掌握回溯算法； 二、实验题 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，n且 w i ? c 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这21?c2i?1艘轮船。如果有，找出一种装载方案。 三、实验提示
void backtrack (int i) {// 搜索第i层结点
if (i > n) // 到达叶结点
更新最优解bestx,bestw;return; r -= w[i];
if (cw + w[i] <= c) {// 搜索左子树 x[i] = 1; cw += w[i];
backtrack(i + 1); cw -= w[i]; } if (cw + r > bestw) {
x[i] = 0; // 搜索右子树 backtrack(i + 1); } r += w[i]; }
?