. ? . ?
思想2: 对n个物品排序
用物品的重量去判断是否需要一只新箱子，如果物品重量小于本箱子所剩的载重量,则装进去,反之则取一只新箱子。
程序:
count=1;qw[0]=TW; for(i=0;i k=0; while(k if(w[i]<=qw[k]) qw[k]=qw[k]-w[i]; code[i]=k; //第i个物品放在第k个箱子内 else {count++; //取一个新箱子 qw[count-1]=TW-w[i]; code[i]=count-1; } } 用贪婪法解背包问题: n个物品，重量:w[n] 价值v[i] 背包限重TW，设计一个取法使得总价值最大. 方法: 0 1 2 3 ? n-1 w0 w1 w2 w3 ? wn-1 v0 v1 v2 v3 ? vn-1 v0/w0 ? v(n-1)/w(n-1) 求出各个物品的\性价比\ 先按性价比从高到低进行排序 已知:w[n],v[n],TW 程序: ? for(I=1;I d[i]=v[i]/w[i]; //求性价比 for(I=0;I for(j=0;j { max=d[j];x=j; } } e[i]=x; d[x]=0; } temp_w=0;temp_v=0; for(i=0;i { if(temp_w+w[e[i]]<=TW) temp_v=temp_v+v[e[v]]; } 分治法: 思想:把规模为n的问题进行分解,分解成几个小规模的问题.然后在得到小规模问题的解的基础上,通过某种方法组合成该问题的解. 例:数轴上有n个点x[n],求距离最小的两个点. 分:任取一点,可以把x[i]这n个点分成两个部分 小的部分 分点 大的部分 |_._.__.__.____._|__._._.__._.__._______._.__._._.__.___._____._| 治:解=min{小的部分的距离最小值; 大的部分的距离最小值; 大的部分最小点和小的部分最大点这两点之差;} 第六天 快考试了， 老师没有多说什么，他只是给我们讲了讲近三年试题情况，并详细讲述了两道题目：一道递归，另一道回溯。不过今天不知怎么回事，我感觉特别累，也特别想睡 觉。所以没什么感觉。这里就不说了，两道题目都有的，递归那题是2001年最后一题,回溯是在《程序员教程》P416，老师说高程曾经考过，有兴趣自己看 看也能看懂的。老师特意为我们出了一份下午试题，我现在把他拿出来让大家参考参考。到这里，就到这里！ 程序员考试下午试题（模拟） 一、把一个字符串插入到另一个字符串的某个位置（指元素个数）之后 char *insert(char *s，char *t，int position) { int i; char *target; if（position>strlen(t)） printf(\ else { for (i=0;i< （1） ;i++) { if (i { if(i< （2） ) target[i]=t[i]; else （3） ; } } } return garget; } 二、辗转相除法求两个正整数的最大公约数 int f(int a,int b) { if (a==b) （4） ; else { if (a>b) return f(a-b,b); else （5） ; } } 三、求一个链表的所有元素的平均值 typedef struct { int num; float ave; }Back; typedef struct node{ float data; struct node *next; } Node; Back *aveage（Node *head） { Back *p,*q; p=（Back *）malloc（sizeof（Back））; if （head==NULL） { p->num=0; p->ave=0; } else { （6） ; p->num=q->num+1; （7） ; } retuen p; } main() { Node *h; Back *p; h=create(); /*建立以h为头指针的链表*/ if (h==NULL) printf(\没有元素\ else { p=aveage(h); printf(\链表元素的均值为：o\ } } 四、希尔排序 已知待排序序列data[n]；希尔排序的增量序列为d[m]，其中d[]序列降序 排列，且d[m-1]=1。其方法是对序列进行m趟排序，在第i趟排序中，按增量d[i]把整个序列分成d[i]个子序列，并按直接插入排序的方法对每个子序列进行排序。 希尔排序的程序为： void shellsort(int *data,int *d,int n,int m) { int i,j; for (i=0;i for (j=0; （1） ;j++) shell( （2） ); } void shell(int *data,int d,int num,int n) { int i,j,k,temp; for (i=1; （3） ;i++) { j=0; temp=data[j+i*d]; while ((j for (k=j;k 五、求树的宽度 所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。本算法是按层次遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。 int Width(BinTree *T) { int front=-1,rear=-1; /* 队列初始化*／ int flag=0,count=0,p;/*p用于指向树中层的最右边的结点，flag记录层中结点数的最大值。*／ if(T!=Null) { rear++; （1） ; flag=1; p=rear; } while( （2） ) { front++; T=q[front]; if(T->lchild!=Null) { rear++; （3） ; count++; } // if(T->rchild!=Null) { rear++; q[rear]=T->rchild; （4） ; } if(front==p) /* 当前层已遍历完毕*/ { if( （5） ) flag=count; count=0; // p=rear; /* p指向下一层最右边的结点*/ } } return(flag); } 六、区间覆盖 设在实数轴上有n个点（x0，x1，??，xn-2，xn-1），现在要求用长度为1的单位闭区间去覆盖这n个点，则需要多少个单位闭区间。 int cover(float x[ ], int num) { float start[num],end[num]; int i ,j ,flag, count=0; for (i=0;i for (j=0;j< （1） ;j++) { if ((start[j]>x[i])&&(end[j]-x[i]<=1)) （2） ; else if ( （3） ) end[j]=x[i]; else if ((x[i]>start[j])&&(x[i] if ( （4） ) { end[count]=x[i]; （5）; count++; } } return count-1; } start[count]=x[i] 七、围棋中的提子 在围棋比赛中，某一方（假设为黑方）在棋盘的某个位置（i，j）下子后，有可能提取对方（白方的一串子）。以W[19][19]表示一个棋盘，若W [i][j]=0表示在位置（i，j）上没有子，W[i][j]=1表示该位置上的是黑子，W[i][j]=-1表示该位置上是白子。可以用回溯法实现提 子算法。 下列程序是黑棋（tag=1）下在（i，j）位置后判断是否可以吃掉某些白子，这些确定可以提掉的白子以一个线性表表示。 问题相应的数据结构有： #define length 19 /*棋盘大小*/ #define max_num 361 /*棋盘中点的数量*/ struct position { int row; int col; }; /*棋子位置*/ struct killed { struct position data[max_num]; int num; } *p; /*存储可以吃掉的棋子位置*/ struct stack { struct position node[max_num]; int top; }; /*栈*/ int w[length][length]; /*棋盘中双方的棋子分布*/ int visited[length][length]; /*给已搜索到的棋子位置作标记，初值为0，搜索到后为1*/