//////////////////////////////////////////////////////////////////////
/*  程序功能：程序算法的實現
    開發思想：利用貪心方法來實現
        
		作者：葛興高
        日期：2004.10.1
        版本：1.1

*/
#include "stdafx.h"
#include "beibao.h"
#include "GreedyBeibao1.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

GreedyBeibao::GreedyBeibao()
{

}

GreedyBeibao::~GreedyBeibao()
{

}
void GreedyBeibao::Sort(DataType A[],int n)//排序
{
	int i,j;
	int flag;
	int b=1;
	DataType k;
	for(int xi=1;xi<=n;xi++)
	//用( type-name )可以強制改變一個數的類型
	A[xi].num=(float)A[xi].Val/(float)A[xi].Wei;	

	for(i=1;i<=n;i++)
	{
		flag=1;
	    for(j=i+1;j<=n;j++)
		{
			if(A[i].num<A[j].num)
			{
				flag=0;
				k=A[i];
				A[i]=A[j];
				A[j]=k;
			}
		}
		if(flag) break;
	}
}
///----------------------------------------
void GreedyBeibao::CinyouSelf(DataType A[],int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		A[i].num1=i;
		cout<<i<<"\t";
		cin>>A[i].Val;
		cout<<"\t";
		cin>>A[i].Wei;
		cout<<endl;
	}
}
////--------------------------------------
void GreedyBeibao::RandA(DataType A[],int n)
{
	int i;
	srand( (unsigned)time( NULL ) );
	for(i=1;i<=n;i++)
	{
		A[i].Val=rand()%30+1;
		A[i].Wei=rand()%30+1;
		A[i].num1=i;
	}
	/*for(int j=1;j<=n;j++)
	{	cout<<A[j].Val<<"\t";
		cout<<A[j].Wei<<"\t";
		cout<<endl<<endl;
	}*/
}
//---------------------------------------------
//int SubSet(int n, int k, bool * flag); 
int GreedyBeibao::SubSet(int n, int k, bool * flag)
{
    int i;
    for(i=n-1;i>=1;i--)
    if(flag[i]&&!flag[i-1])
    {
       flag[i]=0;
       flag[i-1]=1;
       if(flag[n-1]==0)
       {
          int j;
          i++;
          j=n-1;
          while(flag[i]&&!flag[j]&&i<=j)
          {
                flag[i]=0;
                flag[j]=1;
                i++;
                j--;
          }
       }
       return k;
    }
    return -1;
}
//------------------------------------------------
void GreedyBeibao::Greedyresult(int f1[],int f2[],int x[],DataType A[],bool flag[],
				  int &nu,int n,int m,int k,int &result,int &total)
{
	int i;
	///int nu=0;
	int m1=m;
	int v=0;
	int c[101];
	for(i=0;i<=n;i++)
	{x[i]=0;f1[i]=0;}
	for(i=0;i<n;i++)//1--10
		 c[i]=i+1;
	 for(i=0;i<n;i++)//初始把所有置0，即00，0000，0000
		 flag[i]=0;
	 for(i=n-1;i>=n-k;i--)//用于指定k，即選取個數。這里表示00，0000，0111
		 flag[i]=1;
	 if(k!=n){
	 for(i=0;i<n;i++)// 求前K個數的總值
	 {	
		 if(flag[i]==1)
		 {	 
			if(m>=A[c[i]].Wei)
			{
				f1[nu]=c[i];
				m=m-A[c[i]].Wei;
				v=v+A[c[i]].Val;
				x[c[i]]=1;
				nu++;
			}// cout<<c[i]<<" ";//輸出1對應的位置如：00，0000，0111，顯示：8 9 10
		 }
	 }
	 }
	 for(i=1;i<=n;i++)//除K個數以外的數
	 {
		 if(x[i]!=1&&m>=A[i].Wei)
		 {
			 m=m-A[i].Wei;
			 v=v+A[i].Val;
			 x[i]=1;
			 f1[nu]=i;
			 nu++;
		 }
	 }
	 result=v;//記錄尋找一遍以后的最優值
//-------------------------------------------------
	 //cout<<endl;
	 total++;
	while(SubSet(n,3,flag)>0)
	 {   
		 for(i=1;i<=n;i++)
		     x[i]=0;
		 total++;
		   for(i=0;i<=n;i++)
			   f2[i]=0;
		   v=0;
		   m=m1;
		   nu=0;
		 for(i=0;i<n;i++)
		{	
			if(flag[i]==1)
			{
				//cout<<c[i]<<" ";
				if(m>=A[c[i]].Wei)
				{	
					f2[nu]=c[i];
					m=m-A[c[i]].Wei;
					v=v+A[c[i]].Val;
					x[c[i]]=1;
					nu++;
				}
			}
		}
		 for(i=n;i>0;i--)
		 {
			 if(x[i]!=1&&m>=A[i].Wei)
			 {
			 m=m-A[i].Wei;
			 v=v+(int)A[i].Val;
			 x[i]=1;
			 f2[nu]=i;
			 nu++;
			 }
		 }
	//---------------------
	//保存最優值和最優值的編號
		if(result<v)
		{
			for(i=0;i<=n;i++)
			{f1[i]=0;}
			result=v;
			for(i=0;i<=n;i++)
			{f1[i]=f2[i];}
		}
	///---------------------
		//cout<<endl;
	 }//while
}
void GreedyBeibao::BeibaoTime(int f1[],int f2[],int x[],DataType A[],bool flag[],
				  int &nu,int n,int m,int k,int &result,int &total)
{
	LARGE_INTEGER litmp;
	LONGLONG  StartT,EndT;
	double dfMinus, dfFreq, Tresult;
	QueryPerformanceFrequency(&litmp);
	dfFreq=(double)litmp.QuadPart;
	QueryPerformanceCounter(&litmp);
	StartT=litmp.QuadPart;
	Greedyresult(f1,f2,x,A,flag,nu,n,m,k,result, total);
	QueryPerformanceCounter(&litmp);
	EndT=litmp.QuadPart;
	dfMinus=(double)(EndT-StartT);
	Tresult=(dfMinus/dfFreq)*1000;
	cout<<"Time is:"<<Tresult/1000<<"秒"<<endl;
}