程序的灵魂——算法——之贪心

     贪心，一个响亮的名字。可能大家都做过有关贪心算法的题目。

     例如大家熟悉的关路灯（logo就已涉及到了）、种树啊等等......

    下面由我来给大家先介绍一下贪心算法的基本概念：贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，

即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向

下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定

它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整

体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证

明，通过每一步贪心选择，最终可得到问题的一个整体最优解。

  它的思想是：从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步

只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添

加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

    它的过程是：

1.建立数学模型来描述问题；

2.把求解的问题分成若干个子问题；

3.对每一子问题求解，得到子问题的局部最优解；

4.把子问题的解局部最优解合成原来解问题的一个解。

下面举1个例子：

最大乘积问题： 

题目描述

一个正整数一般可以分为几个互不相同的自然数的和，如3=1+2，4=1+3，5＝1+4=2+3，6=1+5＝2+4，…。

现在你的任务是将指定的正整数n分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。

输入输出格式

输入格式：

只一个正整数n，(3≤n≤10000)。

输出格式：

第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。

第二行是最大的乘积。

输入输出样例

输入样例#1： 

10

输出样例#1： 

2 3 5
30

这道题比较有难度，也就是我为什么要发的原因了。自然喽，它是一道很典型的贪心及数论的题目。

下面发一下这道题的解释及答案：

1.

解题思路：

本题要先用简单的数论和贪心找到最优解的组成方法，再用高精度乘法求积。

以2004为例，由于把2004分拆成若干个互不相等的自然数的和的分法只有有限种，因而一定存在一种分法,使得这些自然数的

乘积最大。

若1作因数,则显然乘积不会最大。把2004分拆成若干个互不相等的自然数的和,因数个数越多，乘积越大。为了使因数个数尽

可能地多，我们把2004分成2+3…+n直到和大于等于2004。

若和比2004大1，则因数个数至少减少1个，为了使乘积最大,应去掉最小的2，并将最后一个数（最大）加上1。

若和比2004大k（k≠1）,则去掉等于k的那个数,便可使乘积最大。

例如15：s=2+3+4+5+6刚好大于15，s-15=5，所以把5去掉。

又例如13：s=2+3+4+5刚好大于13，s-13=1,所以去掉2，并把5加1，即3 4 6。

AC 代码及解释如下：

#include <bits/stdc++.h>//万能头文件

using namespace std;const int L = 500;//设置高精度乘法长度为500左右

string mul(string a,string b)//高精度乘法a,b,均为非负整数

{ 

   string s;    int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();//na存储被乘数，nb存储乘数，nc存储积
   

fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);//将na,nb,nc都置为0

   for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';//将字符串表示的大整形数转成i整形数组表示的大整形数

   for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';    for(int i=1;i<=La;i++)        for(int j=1;j<=Lb;j++)

       nc[i+j-1]+=na[i]*nb[j];//a的第i位乘以b的第j位为积的第i+j-1位（先不考虑进位）

   for(int i=1;i<=La+Lb;i++)

       nc[i+1]+=nc[i]/10,nc[i]%=10;//统一处理进位

   if(nc[La+Lb]) s+=nc[La+Lb]+'0';//判断第i+j位上的数字是不是0

   for(int i=La+Lb-1;i>=1;i--)

       s+=nc[i]+'0';//将整形数组转成字符串

   return s;

}string f ( int x ){//f函数用来把任意一个整型数字转化为字符串的形式。

       int i = 0, j;        string p = "";        char ch[10], t;        do{

           ch[i] = x % 10 + '0';

           x /= 10;

           i++;

       }while ( x != 0 );//只要x不为0，就去掉末位。

       ch[i] = '\0';        for ( j = 0, i--; j <= i/2; j++, i-- ){

           t = ch[j];

           ch[j] = ch[i];

           ch[i] = t;

       }     

   return ch;//返回这个字符串

}int n, c = 1, ans[1001];//ans数组用来存拆分的数字

string s[1001], m = "1";//s数组用来存每一个数字的字符串，方便做高精度乘法，m存总乘积，初值为“1”。

int main(){   

 scanf ( "%d", &n );  

  if ( n <= 4 ){      

  printf ( "%d\n%d\n", n, n );       

 return 0;

   }//特判，如果n小于5，自己本身就是最优解。

   for ( int i = 2; i <= n; i++ ){//2到n循环

       if ( n >= i )

       n -= i, ans[c++] = i, s[c-1] = f(i);//每拆分出1个数，n就减去这个数，在用s数组存下等同于这个数的字符串

       else break;//不能再拆分就终止循环

   }    for ( int i = c - 1; i >= 1; i-- )//逆序倒推
  

 if ( n > 0 ) ans[i]++, s[i] = f(ans[i]), n--;//多的数分担给其他数

   if ( n > 0 ) ans[c-1]++, s[c-1] = f(ans[c-1]);//如果还多，就分担给最后一个数

   for ( int i = 1 ; i < c ; i++ ){        cout << ans[i] << " ";//输出每个拆分数

       m = mul ( s[i], m );//每次都将等同于这个数的字符串乘给m

   }    cout << endl << m;//输出总乘积

   return 0;

}