背包问题非递归.c

C语言常用算法 之 背包问题 常用代码 方便使用

#include<stdio.h>
#define N 7
#define S 15

typedef struct  
{
	int s;
	int n;
	int job;
	
}KNAPTP;

int w[N+1]={0,1,4,3,4,5,2,7};

int knap(int s, int n)
{
	KNAPTP stack[100],x;
	int top,k,rep;
	x.s=s;
	x.n=n;
	x.job=0;
	top=1;
	stack[top]=x;
	k=0;
	while (top>=1&&!k)
	{
		x=stack[top];
		rep=1;
		while(!k&& rep)
		{
			if (x.s==0)
			{
				k=1;
			} 
			else
			{
				if (x.s<0||x.n<=0)
				{
					rep=0;
				} 
				else
				{
					x.s=x.s-w[x.n--];
					x.job=1;
					stack[++top]=x;
				}
			}
			
		}
		if (!k)
		{
			rep=1;
			while (top>=1&&rep)
			{
				x=stack[top--];
				if(x.job==1)
				{
					x.s+=w[x.n+1];
					x.job=2;
					stack[++top]=x;
					rep=0;
				}
			}
		}
	}
		
	    if(k)
		{
			while (top>=1)
			{
				x=stack[top--];
				if (x.job==1)
				{
				printf("%4d\t",w[x.n+1]);	
				}
			}
		}
		
	
     return k;
}

void main()
{
	if(knap(S,N)) printf("OK!\n");
	else printf("NO!\n");
}