} if ( valid == TRUE ) printf(\ else printf(\}

void push_stack( stack *topptr, char ch ) { stack newptr; newptr=(struct node * ) malloc( LEN ); newptr->data=ch; newptr->next=*topptr; *topptr=newptr; }

int pop_stack( stack topptr ) { stack tempptr; char popvalue; if (topptr!=NULL ) { tempptr=topptr; popvalue=topptr->data; topptr=topptr->next; free( tempptr ); return popvalue; } else return 0; }

6．用C语言编写背包问题的算法。背包问题的描述是：假设有n件质量分别为w1，w2，?，wn的物品和一个最多能装载总质量是T的背包，问能否从这n件物品中选择若干件物品装人背包，并且使被选物品的总质量恰好等于背包所能装载的最大质量，即Wxl＋Wx2＋?Wxk＝T。若能，则背包问题有解，否则背包问题无解。

#include \

#define NUMBER 20 /*定义物品个数*/ #define TRUE 1 #define FALSE 0

int stack[NUMBER];

int top; void main() { int knapproblem( int, int, int[]); int weight[NUMBER]; /*存放物品质量的数组*/ int n, i; int maxweight; /*包所能承受的最大重量*/ printf(\ scanf(\ printf(\ scanf(\ printf( \ Please input every object's weight :\\n\ for (i=1; i<=n; i++ ) scanf(\if (knapproblem(n, maxweight, weight ) == TRUE ) /*调用背包处理函数*/ { printf(\ printf(\ for ( ;top>0;top-- ) printf(\stack[top],weight[stack[top]]); /*pop stack and print every weight*/ printf(\ } else printf(\} /*main*/

int knapproblem( int n, int maxweight, int weight[] ) /*背包问题处理函数*/ { /*func kanpstack*/ int i=1; top=0; while ((maxweight>0)&&(i<=n)) { if ((maxweight-weight[i]==0) || ((maxweight-weight[i] >0 )&& (i

/*Push No.i stack*/ stack[ ++top ]=i; maxweight = maxweight-weight[i]; } if ( maxweight==0) /*能够装入包中*/ { return( TRUE ); } else if (( i==n )&& (top>0)) /*继续试探*/ { i=stack[top]; top=top-1; maxweight = maxweight+weight[i]; } i++; } /*while*/ return( FALSE ); } /*knapproblem*/

7．划分子集问题的求解。划分子集问题的实际例子很多，如：某个运动会设立n个比赛项目，每个运动员可以参加一到三个项目，考虑到同一运动员参加的项目不能够在同一时间内进行，则如何安排比赛日程才能使总的日程最短。又如：学校开设m科课程，不同的同学可能选修多门不同的课程，在学期末要进行考试，则如何安排这m科课程的考试才能使考试时间最短而又不冲突。

#include \

#define MAX 10 /*元素数目*/

int r[MAX][MAX]; /*存放关系矩阵*/ int n;

int result[MAX]; /*存放分组结果*/

void main() { void division( int [MAX][MAX] ); /*声明划分子集函数*/ int i, j; printf(\ scanf(\ printf(\matrix,1 rash, 0 no rash:\\n\/*输入冲突矩阵,1冲突,0不冲突*/ for ( i=1; i<=n; i++ )

for( j=1; j<=n; j++ ) scanf(\ division(r); /*调用子集划分函数*/ for( i=1; i<=n; i++ ) /*输出分组结果*/ printf(\i, result[i]); }

void division ( int r[MAX][MAX]) { /*子集划分函数*/ int newr[MAX]; /*记录所有以入组的元素发生冲突的元素信息*/ int cq[MAX]; /*循环队列*/ int i, k; int front, rear; /*循环队列头尾指针*/ int group, pre; for (k=0; k<=n-1; k++ ) /*n个元素依此入队列*/ cq[k]=k+1; for ( k=0; k<=n; k++)/*初始状态,均不冲突*/ newr[k]=0; group=1; pre=0; while (( rear != front ) || (rear != 0 )) { front=(front+1)%n; i=cq[front]; if (i