背包问题
实验题目：背包问题
问题描述：假设有一个能装入总体积为T的背包和n件体积分别为w 1, w 2, … , w
n的物品，能否从n件物品中挑选若干件恰好装满背包，即使w 1+w 2+…+ w
n=T，要求找出所有满足上述条件的解。
例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）
（1，4，5） （8，2） （3，5，2）。 概要设计：
采用栈数据结构，利用回溯法的设计思想来解决背包问题。
首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。
ADT Stack {
1 / 9
数据对象：D＝{ ai | ai∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：R1＝{
操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：栈S被销毁。 ClearStack(&S)
初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty(S)
初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回TRUE，否则FALSE。 StackLength(S)
初始条件：栈S已存在。
操作结果：返回S的元素个数，即栈的长度。 GetTop(S, &e)
初始条件：栈S已存在且非空。
2 / 9
操作结果：用e返回S的栈顶元素。 Push(&S, e)
初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。 Pop(&S, &e)
初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。 } ADT Stack 源代码： #include
FILE *fp1,*fp2;//fp1指向数据文件，fp2指向结果文件 typedef struct SqStack{ int *base; int *top; int num; }SqStack;
struct SqStack *S,L;
3 / 9
int InitStack(SqStack *s,int n){ s->base=(int *)malloc(n*sizeof(int)); if(!s->base) exit(0); s->top=s->base; s->num=0; return OK; }//创建栈
int Push(SqStack *s,int m){ *s->top++=m; s->num++; return OK; }//元素入栈
int Pop(SqStack *s,int *p){ if(s->base==s->top)return 0; --s->top; *p=*s->top; s->num--; return OK;
}//元素出栈,用指针p返回 int print(SqStack *s,int w[]){ int *p;
4 / 9
