计算机算法与设计分析实验报告

计算机组织与体系结构——实验报告

cout<

} } else {

for (int i=0;i<=1;i++) {

p[1][t]=i; count+=i;

//确定第一行第t个的值； //用来计算‘-’的个数；

for (int j=2;j<=t;j++) {

p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2]; //第一行大于等于2时确定后面从第

//列中符号，计算‘-’个数；

2行开始增加的一

count+=p[j][t-j+1];

}

}

if (count <= half && (t*(t+1)/2-count) <= half) //约束条件； {

BackTrace(t+1);

}

for (j=2;j<=t;j++) //回溯，判断另一种符号情况； { }

count-=p[j][t-j+1];

count-=p[1][t];

} }

int main() {

cout<<\请输入第一行符号的个数：\cin>>n; count=0; sum=0;

half=n*(n+1)/2; if (half%2==0) {

half=half/2; p=new uchar* [n+1]; for (int i=0;i<=n;i++) {

p[i]=new uchar[n+1];

memset(p[i],0,sizeof(uchar)*(n+1));

13

计算机组织与体系结构——实验报告

} else {

}

BackTrace(1); for (i=0;i<=n;i++) { delete[] p[i]; }

delete[] p;

cout<<\满足要求的三角形符号共有：\个\

cout<<\不存在这样的三角形符号！\

}

return 0;

}

五、实验结果

二：0—1背包问题 一、实验目的与要求

1、掌握0—1背包问题的回溯算法； 2、进一步掌握回溯算法；

二、实验题：

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 三、实验程序 #include using namespace std; class Knap {

friend int Knapsack(int p[],int w[],int c,int n ); public: void print() {

14

计算机组织与体系结构——实验报告

for(int m=1;m<=n;m++) { cout<

cout<

};

private:

int Bound(int i);

void Backtrack(int i); int c;//背包容量 int n; //物品数 int *w;//物品重量数组 int *p;//物品价值数组 int cw;//当前重量 int cp;//当前价值

int bestp;//当前最优值 int *bestx;//当前最优解 int *x;//当前解

};

int Knap::Bound(int i) { //计算上界

int cleft=c-cw;//剩余容量

int b=cp;

//以物品单位重量价值递减序装入物品 while(i<=n&&w[i]<=cleft) { cleft-=w[i]; b+=p[i];

i++;

}

//装满背包

if(i<=n) b+=p[i]/w[i]*cleft; return b;

}

void Knap::Backtrack(int i) { if(i>n) { if(bestp

for(int j=1;j<=n;j++)

15

计算机组织与体系结构——实验报告

bestx[j]=x[j];

bestp=cp; } return; }

if(cw+w[i]<=c) //搜索左子树 { x[i]=1; cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i];

}

if(Bound(i+1)>bestp)//搜索右子树 { x[i]=0;

Backtrack(i+1);

}

}

class Object

{ friend int Knapsack(int p[],int w[],int c,int n); public: int operator<=(Object a)const {

return (d>=a.d); } private: int ID; float d; };

int Knapsack(int p[],int w[],int c,int n) { //为Knap::Backtrack初始化 int W=0; int P=0;

int i=1;

Object *Q=new Object[n]; for(i=1;i<=n;i++)

{

Q[i-1].ID=i;

Q[i-1].d=1.0*p[i]/w[i]; P+=p[i];

16

计算机组织与体系结构——实验报告

W+=w[i]; }

if(W<=c) return P;//装入所有物品 //依物品单位重量排序 float f;

for( i=0;i

for(int j=i;j

Q[j].d=f;

}

} Knap K;

K.p = new int[n+1]; K.w = new int[n+1]; K.x = new int[n+1]; K.bestx = new int[n+1]; K.x[0]=0; K.bestx[0]=0; for( i=1;i<=n;i++) { K.p[i]=p[Q[i-1].ID];

K.w[i]=w[Q[i-1].ID];

}

K.cp=0;K.cw=0; K.c=c;K.n=n;

K.bestp=0;//回溯搜索 K.Backtrack(1);K.print(); delete [] Q;delete [] K.w; delete [] K.p;

return K.bestp;

} void main()

{ int *p;int *w; int c=0;int n=0;int i=0; cout<<\请输入背包个数：\ cin>>n;

p=new int[n+1]; w=new int[n+1];

p[0]=0;w[0]=0;

17