《算法笔记》总结No.6——贪心

一.简单贪心

        贪心法是求解一类最优化问题的方法，它总是考虑在当前状态下局部最优(或较优)之后，来使全局的结果达到最优(或较优)的策略。显然，如果采取较优而非最优的策略(最优策略可能不存在或是不易想到)，得到的全局结果也无法是最优的。而要获得最优结果，则要求中间的每步策略都是最优的，因此严谨使用贪心法来求解最优化问题需要对采取的策略进行证明。证明的一般思路是使用反证法及数学归纳法，即假设策略不能导致最优解，然后通过一系列推导来得到矛盾，以此证明策略是最优的，最后用数学归纳法保证全局最优。不过对平常使用来说，也许没有时间或不太容易对想到的策略进行严谨的证明(贪心的证明往往比贪本身更难)，因此一般来说，如果在想到某个似乎可行的策略之后，并且自己无法举出反例，那么就勇敢地实现它。

1.组个最小数

给定数字0~9各若干个，可以任意顺序排列这些数字，但必须全部使用，且使目标数字尽可能小（当然0不能做首位）比如输入两个0、两个1、三个5和一个8，得到的最小数字就是100155858。

相信大家一下子就可以看出来策略：先从1~9中选择不为0的最小数输出，然后从0~9输出数字，每个数字输出次数为其剩余个数。

策略正确的证明：

• 首先由于所有数字都必须参与组合，因此最后结果的位数是确定的。 
• 由于最高位不为0，则选一个尽可能小的数作为首位——最高位定理
• 其余位数也应该从小到大输出~

  教材上的实在是太抽象了，好像有点错误，这里博主自己写了一种：

  #include 
  #include 
  #include  
  #include 
  using namespace std;
  int main() {	
  	vector V;
  	for(int i=1;i>temp;
  		V.push_back(temp);
  	}
  	sort(V.begin(),V.end());  //直接排成升序 
  	int flag=0;  //标记 
  	for(int i=0;i