算法设计与分析实验报告

for( i=1;i

cin>>w[i]; }

loadling(x,w,c,n); return; }

（4） 编程实现背包问题的求解。 （P94） void Sort(int n,float v,float w) {//按单位价值为物品排序 float l[] = v/w+v%w;

void bubblesort(sqlist &l) {//冒泡排序

int lastexchangeindex; int i,j;

RcdType temp[20]; i=l.length; while(i>1) {

lastexchangeindex=1; for(j=1;j

temp[j]=l.r[j]; l.r[j]=l.r[j+1]; l.r[j+1]=temp[j];

lastexchangeindex=j; }

i=lastexchangeindex; } } }

void Knapsack(int n,float M,float v[],float w[],float x[]) {

Sort(n,v,w); int i;

float c = M;

for(i = 1;i <= n;i++) x[i] = 0; //初始化 x[i] for(i = 1;i <= n;i++) {

if(w[i]>c) break; x[i] = 1;

c-=w[i]; }

if(i<=n)

x[i] = c/w[i]; return; }

（5） 编程实现多机调度问题的求解。 （P106）

（6） 设计算法求解汽车加油问题，并编程实现。（P111，算法实现题 4－9）； #include

void greedy(int d[],int n,int k) { int num = 0; //加油次数 for(int i = 0;i <= k;i++)

{//若加油站距离大于最大行驶距离，则无解 if(d[i] > n) {

printf(\ return; } } int s = 0;

for(i = 0;i <=k;i++)

{//若下站与下下站距离之和大于最大行驶数，则加油，反之不加 s += d[i]; if(s > n) { num++; s = d[i]; } }

printf(\ }

void main() { int i,n,k,d[1000];;

//最多行驶 n 千米，k 个加油站，每个加油站距离 d[]; printf(\请输入汽车加满油最大行驶距离\\n\ scanf(\

printf(\请输入加油站个数\\n\ scanf(\

printf(\请依次输入每个加油站距上一站距离\\n\ for(i = 0;i <= k;i++)

scanf(\ greedy(d,n,k); return; }

（7） 设计算法求解删数问题，并编程实现。（P112，算法实现题 4-11）； （8） 设计算法求解数列级差问题，并编程实现。

注：至少选择其中 3 题完成。 3.主要仪器设备及软件 （1） PC 机

（2） TC、VC++、Java 等任一编程语言 实验五 回溯法及其应用

（验证型、设计型实验 6 学时） 1.目的要求：

（1） 理解回溯法的深度搜索策略，掌握用回溯法解题的算法框架； （2） 掌握设计回溯算法的基本技巧和实际问题的分析求解。 2.实验内容：

（1） 设计算法从前 m 个大写字母(m≤26)种取出 n 个字母的所有排列（组合）， 并编程实现。

（2） 设计算法求解子集合问题，并编程实现。 （P151，算法实现题 5-1） （3） 设计算法求解工作分配问题，并编程实现。（P156，算法实现题 5-13） （4） 设计算法实现 0－1 背包问题，并编程实现。（P159，算法实现题 5-22） （关键代码）

/*************0-1 背包改进算法***********/ int bestp;//最优结果

/*************限界函数***********/ int bound(int i,int cw,int cp) {

cw+=x[i]*w[i]; cp+=x[i]*p[i]; int cleft=c-cw; int b=cp;

for(int j=i+1;j<=n&&w[j]<=cleft;j++) {

b+=p[j]; cleft-=w[j]; }

if(j

b+=p[j]*(cleft)/w[j]; return b; }

bool check(int i,int cw,int cp) {

if((cw+x[i]*w[i]>c)||(bound(i,cw,cp)

void output(int i) {

cout<

/*************功能函数***********/ void tryload(int i;int cw;int cp)

{//cw 当前背包容量,cp 当前背包价值 if(i>n)

{//输出一个可行解 output(i); }else

for(int j=1;j>=0;j--) {

x[i]=j;

if(check(i,cw,cp)) {

cw+=x[i]*w[i]; cp+=x[i]*p[i];

tryload(i+1,cw,cp); cw-=x[i]*w[i]; cp-=x[i]*p[i]; } } }

/*************主函数***********/ void main() {

tryload(1,0,0); }

（5） 设计算法求解旅行售货员问题，并编程实现。 （P139） 关键代码

#include \ #include \ #define noedge 10000

int n,*bestx,**a,bestc; //顶点数,最优解，G 的邻接矩阵，最优值 /*******主函数*************/ void main() {

getdata(); bestc=noedge; for(int i=1;i<=n;i++) bestx[i] = x[i] = i; traveling(2,0); cout<

for(int i=1;i<=n;i++) cout<