内容发布更新时间 : 2025/3/11 15:14:26星期一 下面是文章的全部内容请认真阅读。
} 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)) /*继续试探*/ {