knap_main.cpp

knap2 背包问题非递归

//Knap_main.cpp
//uuhorse
//2008.06.03

#include <stdio.h>
#define TW 10	//背包总量
#define N 6		//货物总数

typedef struct 
{
	int cap;	//背包当前容量
	int ni;		//下个装入物品的下标
}Knap;


int knap(int tw,int n, int w[N])   
{
	int solve=0;
	int top=0;
	Knap stknap[N+2];	//0号单元未用
	stknap[top].ni = n;	//从尾部计算
	stknap[top].cap = tw; 

	while (top>=0 /*&& stknap[top].cap != 0*/)	//未找到一组解
	{
		if (stknap[top].cap-w[stknap[top].ni] <0)
		{
			stknap[top].ni--;	//考虑下一个物体
		}
		else if (stknap[top].cap-w[stknap[top].ni] >0)	//入栈，考虑下一个物体
		{
			stknap[top+1].cap = stknap[top].cap-w[stknap[top].ni];
			stknap[top+1].ni= stknap[top].ni-1 ;
			top++;
		}
		else
		{
			top++;
			stknap[top].cap=0;
			stknap[top].ni=n+1;//向上溢出，只为区分下面向下溢出
		}

		if (stknap[top].ni<0 || stknap[top].cap == 0)	//下标溢出，退栈
		{
				if (stknap[top].cap == 0)	//////////////////////////////
				{
					solve++;	//找到一组解
					int tmp=top;
					while (tmp>0)
					{
						tmp--;
						printf ("%5d", w[stknap[tmp].ni]);
					}
					printf ("\n");
				}							/////////////////////////////////
			top--;
			stknap[top].ni--;
		}
	}

/*	if (top==-1)
	{
		return false;
	}
	if (stknap[top].cap == 0)
	{
		while (top>0)
		{
			top--;
			printf ("%5d", w[stknap[top].ni]);
		}
		printf ("\n");
	}
	return true;*/
	return solve;
}


int main ()
{
	int w[N]={1, 8, 4, 3, 5, 2};

	printf("Found %d solutions!\n",knap(TW, N-1, w));

	return 0;
}