贪心策略&典型题目C++实现

使用贪心策略解决问题

  
  贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

  贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

  贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

  一般情况下，不会验证贪心策略的准确性，需要用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。有些证明是一眼能看出来的，但是有些证明非常麻烦，所以一般是想一些贪心策略然后用对数器进行验证。

  贪心策略与动态规划的区别：贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。

1 给定一个字符串类型的数组strs，找到一种拼接方式，使得把所有字符串拼起来之后形成的字符串具有最低的字典序。

  字典序，。
  在这里，比较策略就是贪心策略。证明的时候，首先要证明比较策略是有效的，然后还要证明根据这个规则排序后，数组中元素拼接起来得到的是最小的字典序，证明比较麻烦，参考剑指offer P229。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compareStrings(string str1,string str2)
{
   
    return (str1+str2)<(str2+str1);
}

string MinOrder(vector<string> strs)
{
   
    if(strs.size() <=0)
        return "";
    sort(strs.begin(),strs.end(),compareStrings);
    string res = "";
    for(int i=0;i<strs.size();i++)
    {
   
        res = res + strs[i];
    }
    return res;
}


int main()
{
   
    cout << "Hello world!" << endl;
    vector<string> strs = {
   "b","ba","abcd","dad","bird"};
    string result = MinOrder(strs);
    cout<<result<<endl;
    strs = {
   };
    result = MinOrder(strs);
    cout<<result<<endl;
    
    return 0;
}

剑指offer上一个类似的题目，不一样的是将整数数组转换为字符数组：

2 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

class Solution {
   
public:
    static bool cmp(int a,int b){
   
         string A="";
         string B="";
         A+=to_string(a);
         A+=to_string(b);
         B+=to_string(b);
         B+=to_string(a);
          
         return A<B;
     }
    /**
    sort中的比较函数compare要声明为静态成员函数或全局函数，不能作为普通成员函数，
    否则会报错。 因为：非静态成员函数是依赖于具体对象的，而std::sort这类函数是全局的，
    因此无法在sort中调用非静态成员函数。静态成员函数或者全局函数是不依赖于具体对象的, 可以访问，
    无须创建任何对象实例就可以访问。同时静态成员函数不可以调用类的非静态成员。
    **/
     string PrintMinNumber(vector<int> numbers) {
   
         string  answer="";
         //将整个数据按照什么情况进行排序
         sort(numbers.begin(),numbers.end(),cmp);
         for(int i=0;i<numbers.size();i++){
   
             answer+=to_string(numbers[i]);
         }
         return answer;
     }
};

3 切金条，使分割代价最小。

题目：一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。一群人想整分整块金 条，怎么分最省铜板？
例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60. 金条要分成10,20,30三个部分。 如果， 先把长度60的金条分成10和50，花费60 再把长度50的金条分成20和30，花费50 一共花费110铜板。但是如果， 先把长度60的金条分成30和30，花费60 再把长度30金条分成10和20，花费30 一共花费90铜板。
要求：输入一个数组，返回分割的最小代价。
   这个题目是一个典型的哈夫曼树的应用，给定$n$个权值作为$n$个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。而这个题目刚好给定了要划分的金条的长度，因为划分时会花费与长度一样的铜板，所以这个长度就可以看做是权值，我们需要给出一个切割顺序使得最后付出的代价最小。
  那么怎么来构造这个哈夫曼树呢。一颗哈夫曼树的样子应该如图所示

  可以看到，权值较大的结点离根较近。为了实现这个我们借用推的结构创建一个小根堆，每次从小根堆中取出来最小的两个值构造叶子节点结合，例如10和20得到30，然后将20放回小根堆，这时小根堆会自动调整形成标准小根堆。然后再从小根堆取出来两个最小的，30,30，计算得到结果60，将60放回小根堆，这时小根堆只剩下一个元素了，停止。每次产生的低价和就是最后结果，即30+60=90。注：哈夫曼树很好用，可以应用于给出权重（代价）得到最小路径的题目，也就是由一些代价生成最小代价。