beibao.cpp

背包问题的解决

#include"Node.h"
#include"linkedstack.h"
#include"beibao.h"
#include<iostream>

using namespace std;

void beibao::loading(int *w,int T,int &k)
{
	int sum,next,last,out;  
	for(int i=0;i<n;i++)
	{	
		int p;
		while(top)s.Delete(p);
		s.Add(w[i],i);
		sum=w[i];
		next=i+1;
		while(1)
		{
			if(next<=n-1)
			{
				if((sum+w[next])>=T)
				{
					if(sum+w[next]==T)
					{
						s.Add(w[next],next);
						store(s,k);
						next++;
						s.Delete(out);
						
						continue;
					}
					else
					{
						next++;
						continue;
					}
				}
				else
				{
					s.Add(w[next],next);
					last=next;
					next++;
					sum=sum+w[next];
					continue;
				}
			}
			else
			{
				if(top->data==w[i])
				{
					if(i==n-1)
					{
						if(sum==T){store(s,k);break;}
						else break;
					}
					else break;
				}
				else
				{
					int temp;
				s.Delete(out);
				sum=sum-out;

				/*for(int j=0;j<n;j++)
				{
					if(w[j]==s.Top())
					{temp=j;break;}
				}
				next=temp+1;*/
				next=s.last()+1;
				continue;
				}
			}
		}
	}
}

void beibao::store(linkedstack &s,int &k)
{
	int temp;
	int j=0;
	while(top)
	{
		s.Delete(temp);
		cout<<temp<<' ';
		a[j]=temp;
		j++;
	}
	cout<<endl;
	for(int i=j-1;i>=0;i--)
	s.Add(a[i]);
	k++;
	
}