用C语言实现背包问题求解。

假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求找出所有满足上述条件的解。

例如：当T=10，各件物品的体积

{1，8，4，3，5，2}时，

可找到下列4组解：（1，4，3，2）（1，4，5） （8，2）（3，5，2）

要求利用栈实现，语言为C。

#include<stdio.h>
#define OK 1
#define ERROR 0
#define SElemtype int
#define STACKSIZE 100

typedef struct{
SElemtype data[STACKSIZE];
int top;
} SqStack;

SElemtype Initstack(SqStack &s)//初始化栈。
{
s.top=0;
return OK;
}

SElemtype Push(SqStack &s,SElemtype e)//入栈。
{
s.data[s.top++]=e;
return OK;
}

void main()
{
int i,n,totalvol,w[STACKSIZE],sum=0,j=0;
SqStack s;
Initstack(s);
printf("请输入背包能装入的总体积：");
scanf("%d",&totalvol);
printf("请输入物品件数：");
scanf("%d",&n);
printf("请输入每件物品的体积：");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
while(s.top!=-1)
{

if(sum+w[j]<=totalvol)
{
Push(s,j);
sum+=w[j];
}

if(sum==totalvol) //找到一组，退栈顶，找下一组。
{
for(i=0;i<s.top;i++)
printf("%d ",w[s.data[i]]);
printf("\n");

s.top--;
sum-=w[s.data[s.top]];
j=s.data[s.top]+1;
}

else
j++;

while(j==n) //遍历后仍未找到，则退栈。
{
s.top--;
sum-=w[s.data[s.top]];
j=s.data[s.top]+1;
}

}

}

http://wenwen.soso.com/z/q160527925.htm

这边刚给你解决了。