linerarange.cpp

动态规划方法视线特殊的（0

#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;  
}