[color=FF0000]我们最近在搞数据结构设计上机实践,
搞了几天晕头转向,希望那位高手能指点一二.
题目: 假设有一个能装入总体积为T的背包和n件体积为w1,w2...wn的物品,能否从n件物品中挑选若干件恰好装满背包,即w1+w2+w3+...+wn=T 要求找出所以满足条件的解;
要求用栈的原理;
本人胡乱编了一个 但总是有错误.望各位指点下 或直接给我个完整程序更好;
程序如下:[/color] #include<stdio.h>
#define INITSIZE 100
typedef int ElemType;
typedef struct
{int top;
ElemType *base;
int stacksize;
}sqstack;
void initstack(sqstack *s)
{s->base=(ElemType *)malloc(INITSIZE*sizeof(ElemType));
s->top=0;
s->stacksize=INITSIZE;
}
int push(sqstack *s,ElemType x)
{if(s->top>s->stacksize)
{s->base=(ElemType*)realloc(s->base,(s->stacksize+1)*sizeof(ElemType));
if(!s->base)return 0;
s->stacksize++;
}
s->base[s->top++]=x;
return 1;
}
int pop(sqstack *s,ElemType *e)
{if(s->top==0)return 0;
*e=s->base[--s->top];
return 1;
}
stackempty(sqstack s)
{if(s.top==0) return  1;
else  return 0;
}
 
int knapsack(int w[],int T,int n)
{ sqstack s; int k=0;
initstack(&s);
do{
          while (T>0&&k<n)
              if (T-w[k]>=0)  { Push(S,k);T-=w[k]; }
              else  k++;
          if (T==0)  { Print(S)；return 1;}
          else  if (!StackEmpty(S)){
                      Pop(S,k)；T+=w[k]; k++;
                  }
     }while (!StackEmpty(S)||k<n)；
     return 0;
}
void main()
{int i,w;
w=malloc(n*sizeof(int));
 for(i=0;i<n;++i)
    {    scanf("%d",W+i);
knapsack(int w[],int T,int n);
}