#include <cstdlib>
#include <iostream>
#include <math.h>

using namespace std;

int Find_Max(int a[],int n,int &pos)    //獲得數組a中的最大值的位置
{
	int mark,i,tempmax;
	tempmax=a[0];
	mark=0;
	for(i=1;i<n;i++)
	{
		if(tempmax<a[i])
		{
			 tempmax=a[i];
			 mark=i;
		}
	}
	pos=mark;
	return tempmax;
}   

void LinerArange(int M,int p[],int w[],int n)
{  //M為邊界值，p為利潤數組，w為物品的權值數組，n為物品的數量
	int i,j,k;
	
	int **F = new int*[n+1];//聲明矩陣保存權值信息
    for(i=0;i<n+1;i++)
      F[i]=new int[M+1];

	int **location = new int*[n+1];//聲明矩陣保存動態尋徑信息
    for(i=0;i<n+1;i++)
       location[i]=new int[M+1];
    
	for(i=0;i<=M;i++)//不取物品時的利潤值初始化
	{
	   F[0][i]=0;
	   location[0][i]=0;
	}

	for(k=1;k<=n;k++)//依次求當考慮第k個物品時的情況
	{
		for(j=0;j<=M;j++)//在重量達到j時的最優值
		{
			if(j<w[k])   //不能取第k個物品
			{
			  F[k][j]=F[k-1][j];
			  location[k][j]=0;
			}
			  
			else if((w[k]<=j) && (j<(2*w[k])))	//對取第k個物品和不取第k個物品的利潤值進行比較取舍	
			{
				if(F[k-1][j] > (F[k-1][j-w[k]]+p[k]))
				{
					F[k][j]=F[k-1][j];
					location[k][j]=0;//未取第k個物品
				}
				else
				{
					F[k][j]=F[k-1][j-w[k]]+p[k];
					location[k][j]=1;//第k個物品取了一個
				}
				 
			}
				 
		  else if(j>=2*w[k] && j<=M)
		  {
		     F[k][j]=max(max(F[k-1][j],F[k-1][j-w[k]]+p[k]),F[k-1][j-2*w[k]]+2*p[k]);	//對取2個第k個物品或取1個第k個物品或不取第k個物品的情況進行權衡	
			 if(F[k-1][j]>F[k-1][j-w[k]]+p[k])
			 {
				 if(F[k-1][j]>F[k-1][j-2*w[k]]+2*p[k])//F[k-1][j]最大
					 location[k][j]=0;
				 else 
					 location[k][j]=2;//F[k-1][j-2*w[k]]+2*p[k]最大
			 }
			 else if(F[k-1][j-w[k]]+p[k]>F[k-1][j-2*w[k]]+2*p[k])
				 location[k][j]=1;//F[k-1][j-w[k]]+p[k]最大
			 else 
				 location[k][j]=2;//F[k-1][j-2*w[k]]+2*p[k]最大
			
		  }
		}
		int pos;
		int *seq=new int[k+1];
		int tempmax=Find_Max(F[k],M+1,pos);
		cout<<"取前"<<k<<"個物品可獲得的最大利潤為"<<tempmax<<endl; 
		for(int kk=k;kk>0;kk--)
		{
            seq[kk]=location[kk][pos];
			pos=pos-w[kk]*seq[kk];
		}
		cout<<"物品的取舍權值情況為：";
		for(int kk=1;kk<=k;kk++)
		{
			cout<<"物品"<<kk<<"取了"<<seq[kk]<<"個  ";
		}
		cout<<endl<<endl;
		delete seq;
	}
}

void main(int argc, char *argv[])
{
	  int w[4]={0,2,3,4};
	  int p[4]={0,1,2,5};
	  int i;
	  cout<<"物品的重量情況和利潤情況為："<<endl;
	  cout<<"重量:";
      for(i=0;i<3;i++)
	     cout<<"W"<<i<<"="<<w[i]<<"    ";
	  cout<<endl<<"利潤:";
      for(i=0;i<3;i++)
	     cout<<"P"<<i<<"="<<p[i]<<"    ";
	  cout<<endl;
	  LinerArange(6,p,w,3);	
	  cin>>i;  
}