最优分解问题.cpp

最优分解问题的贪心算法,使用输入与输出文件来控制程序的输入与输出

/*   
  根据乘法原理，本题的实质是求N   的所有不同   
  拆分数的乘积的最大值。因此可以采用动态规   
  划的思想：   
          F(1)=1   
          F(2)=2   
          F(3)=3   
          F(4)=4   
          F(n)=MAX(n,F(1)*(n-1),F(2)*(n-2),……,F(i)*(n-i))   
              其中(n-i)大于N=i的解中最大的元素   
  列出前几个N发现如下规律：   
          当(sqrt(N*8+17)-1)/2为整数时：   
                  解当中最大的元素比N-1中的大一   
          否则解当中最大的元素是：   
                  (int)((sqrt(N*8+9)-1)/2)   
  证明略*/   
  #include   <stdio.h>   
  #include   <math.h>  
  #include   <fstream>
  #include   <iostream>
  using namespace std;
  main()   
  {   
	  unsigned   int   n;   
      int   g[500],*p=g,l=0;   
      float   t;   
	  long result=1;
      ifstream input("input.txt");
      ofstream output("output.txt");
      input>>n;   
      if   (n>=0   &&   n<=4)   
		  output<<n<<"\n";                 /*如果N小于5直接打印出N*/   
	  else
	  {   
		  t=sqrt((long)n*8+17);   
		  if   (t==(int)t)
		  {   
			  l=1;n--;   
		  }   
		  while(n>=4)
		  {                         /*从后往前推出结果*/   
			  t=sqrt((long)n*8+9);   
			  if   (t==(int)t)   
				  *p=(t-1)/2;   
			  else   
				  *p=(int)((t-1)/2)+1;   
			  n-=*p;p++;   
		  }   
		  *p=n;   
		  if   (l==1)  
			  g[0]++;   
		  for   (l=p-g;l>=0;l--)  
		  {
			  output<<g[l]<<" ";     /*打印结果*/   
			  result*=g[l];
		  }
	  }   
	  output<<"\n最大乘积是："<<result<<endl;
  }