bag_stack.cpp

这是经典的背包问题

#include<iostream.h>
////////////////////////////////////////////////////////////////////////////////
//用栈实现
int n;//number of items
int*item;//pointer to the items' array
int t;//total capability


void bag_judge();
bool bag_recursion_stack();
//////////////////////////////////////////////////////////////////////////
class mystack
{
private:
    int group[102];
	int curr;
public:
	mystack(){curr=-1;}
	~mystack(){};
	bool isempty();
	void  push(int);
    void  pop();
	int gettop();
	int getbottom();
};

bool mystack::isempty()
{
	if (curr<0)
		return 1;
	return 0;
}

void mystack::push(int x)
{
   if(curr<100)
	  group[++curr]=x;
}
void mystack::pop()
{
	if(curr>-1)
		curr--;
}
int mystack::gettop()
{
	if (curr>-1)
		return group[curr];
	else
		return 0;
}
int mystack::getbottom()
{
	return group[0];
}

////////////////////////////////////////////////////////////////////////////////
void bag_judge()
{
	cout<<"put in the number of the items and the total capability of the bag"<<endl;
	cin>>n>>t;
	item=new int[n+5];
	cout<<"put in the weight of each item"<<endl;
	for(int i=1;i<=n;i++)
		cin>>item[i];
	if(bag_recursion_stack())
		cout<<"yes"<<endl;
	else
		cout<<"no"<<endl;
	delete [] item;
}

//////////////////////////////////////////////////////////////////////////

bool bag_recursion_stack()
{
	item[n+1]=0;
	mystack a;
	int sum=0;
	a.push(1);
	sum+=item[1];
	while(a.getbottom()<=n)
	{
		if (sum<t)
		{
			if (a.gettop()<=n)
			{
				a.push(a.gettop()+1);
				sum+=item[a.gettop()];
			}
			else
			{
				sum-=item[a.gettop()];
				a.pop();
				int temp=a.gettop();
				sum-=item[temp];
				a.pop();
				a.push(temp+1);
				sum+=item[temp+1];
			}
		}
		else
			if(sum==t)
				return 1;
		else
		{
			int temp2=a.gettop();
			sum-=item[temp2];
			a.pop();
            a.push(temp2+1);
			sum+=item[temp2+1];
		}
	}
	return 0;
}


void main()
{
	bag_judge();
}