用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;
}

}

}

嘿嘿，跟楼上的差不多啦。

#include<stdio.h> int main() { int total;//总体积。 int a[100],n;//各个体积和总数。 int i,j ; int stack[100],top,sum;//栈(存对应的下标)，栈顶指针,栈内总体积。 scanf("%d%d",&total,&n);//输入总体积和个数。 for(i=0;i<n;i++) scanf("%d",&a[i]);//输入各个体积。 top=0; sum=0; j=0; while(top!=-1) { if(sum+a[j]<=total) //入栈 { sum=sum+a[j]; stack[top]=j; top++; } if(sum==total) //找到一组后，就把栈顶退了。找下一个合适的。 { for(i=0;i<top;i++) printf("%d ",a[stack[i]]); printf("\n"); top--; sum=sum-a[stack[top]]; j=stack[top]+1; } else { j++; } while(j==n) //遍历数组后，找不到合适的，再从循环退栈。 { top--; sum=sum-a[stack[top]]; j=stack[top]+1; } } return 0; }

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息