5、第五章 第二次培训：贪心算法 ...
-
周六晚上，李向南在群里问大家周日有没有时间继续去机房学习，这次大家居然纷纷推脱，王小铭说自己一般都在周日写所有作业，林落落说自己要和父母出去玩，程凯说自己要上补习班，高峰还没回复。
李向南想，估计是今天的培训吓到他们了，一学就在电脑桌前的小转椅上坐四小时，天天这样那得腰酸背疼头晕眼花。不过虽然这样，他还是有一点老父亲被嫌弃的失落感。为了第二次培训，他都做好ppt了。
突然，他收到一条私聊。
鸽比乌斯反演：我去。
鸽比乌斯反演：我还想听学长讲解。
李向南顿时受到了安慰，你看，不愧是学霸，还是很热爱学习的！不过就两个人的话，去机房有点浪费。
Void：要不你去我家或者我去你家。
Void：机房我们两个人用有点浪费。
鸽比乌斯反演：好。就去学长家吧。
这人也答应的太快了？！李向南想。
到了周日，两人依然在学校大门口碰面，碰面之后李向南直接带着高峰到了自己家。
此时此刻，他的父母都在上班，家里一个人也没有。李向南让高峰进了他的书房，帮他打开电脑，然后自己去整了一些水果零食给他吃。
高峰正在瞎摆弄李向南的电脑的时候，李向南端着一盘子零食水果进来了，放在了电脑桌前。
“我们今天来学一下贪心算法吧。”李向南说，然后从客厅又搬来了一个凳子放在电脑面前，打开了ppt。
贪心算法，又称贪婪算法，是指在求解问题的时候，每一步都做出局部最优的选择，最后得出整体最优解。贪心算法虽然说是算法，但是其实更是一种策略，因为对于每一道题，选择贪心的方式是不同的，同时，贪心问题的两大难点也是，一，如何判断这是一个贪心问题，二，如何选择正确的贪心方式。
李向南选择讲解这个，也是因为这个算法比起讲解，更重要的是通过例题锻炼自己的思维能力，所以也不怕单独给高峰一个人开小灶造成他和其他人实力差别太大。
他先拿出了一道例题：“设有n个正整数,将他们连接成一排,组成一个最大的多位整数。例如:n=3时,3个整数13,312,343,连成的最大整数为:34331213。本题要求输入n个正整数，求那个最大多位整数。”
“高峰，你觉得这道题应该怎么解呢？”
高峰看了看这道题。他开始觉得应该先把最大的数放在最前面，但是看着学长这一脸轻松的样子，总觉得没那么容易。他从包里拿出草纸，开始写写画画。很快，他找到了反例：12和121，如果121在前，是12112，12在前是12121，明显12在前的数更大。
他又想了半天，例如把小的数放在前面，但是感觉都不对。
看到学弟一脸焦头烂额的样子，学长微微一笑：“其实这题，也不难的，我来讲一下吧。”
高峰：总觉得学长有点腹黑……
“正确的做法是，把整数转化为字符串，用字符串比较方法比较a+b和b+a的大小，哪个大就采用哪个。”
看着学弟还是有点懵逼的样子，李向南突然暗叫不好：“你知道什么是字符串比较吗？”
“……”
“那你知道什么是字符串吗？”
“知道。”高峰强装镇定，“字符串比较我本来是会的，因为没不怎么用就没反应过来。”
他心中暗想：回去就恶补这方面知识！
不知道为什么，他总希望自己什么方面都能做让学长最满意的那个，无论是学习态度还是学习能力。
李向南还是有些不放心。毕竟大家一开始编程都是用整形数据，字符和字符串操作有一定难度。他拍了拍高峰肩膀：“现在不会也没关系，我希望你能学到贪心的思想，所以代码写不出来也没事。我们先看下一道题吧。”
“有若干个活动，第i个开始时间和结束时间是[Si,fi)，只有一个教室，活动之间不能交叠，求最多安排多少个活动？”
这道题高峰也想了很久。是优先选择什么样的活动呢？是开始时间早的，还是开始时间和结束时间的平均值早的活动呢？
最后，他发现，答案可能是尽量选择结束时间早的活动。但是，他总觉得不太合理，具体为什么不合理他有点说不上来，但是也不知道怎么证明它是正确的方法。
李向南好像看出了他的顾虑：“贪心问题很多情况需要证明策略的正确性，但是证明不出来也不要强求。只要自己认为正确就按这个写。毕竟算法竞赛是要有技巧的。”
高峰点点头，记在了心里。
李向南看了看他：“要是还没有思路，回去可以看看ppt，ppt上有所有例题的题解。我们先看下一道题。”
下一道题李向南埋了个坑。虽然他在讲贪心专题，但是现实中比赛打题的时候可不是题目还告诉你用什么算法的，得靠自己识别用什么算法。所以他下面这道题根本不是贪心的题。
“有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？”
高峰开始感觉这道题好像比较简单，他先试了试优先选择价值大的东西，但是显然不合理，因为有的物体可能价值大重量也大，而别的物体可能重量很小，但是价值和它差不多显然选那个重量小的物体划算。那光选重量小的呢？这肯定也不行。那要是选价值和重量的比最大的呢？这样看起来可以，但是要是考虑到两个物体价值和重量比相等，那该选哪个？
李向南见他没反应，便告诉他真相：“这题不是贪心算法的题，要用后面学的动态规划来解决。这道题属于动态规划中经典的01背包问题。所以记得是不是贪心问题要自己学会判别，不能想当然。”
高峰：“嗯，明白了。”
李向南站了起来：“你先做一会题，我去给你再弄点吃的。”他走出了书房。
高峰坐到了电脑桌面前，双击开浏览器界面找题。突然，他对学长的电脑产生了一点好奇。
据说男生会在自己的电脑里放小黄片，学长会放吗？
高峰自己只是个普通高中生，显然是没有独立使用的电脑的，但是李向南这个电脑桌面是二次元美少女，而且可能是为了更酷炫，他桌面一个图标也没有，这样的电脑显然是个人使用的可能性更大。
他先点开“计算机”图标，打开c盘，开始一个文件夹一个文件夹地找。找了半天，他没找到小黄片，到是找到了不少一看就很高深的算法详解。不愧是学长，他心想。
突然，他看到了一张照片。
照片上，两个男生亲密地搂着肩，其中一个还比着剪刀手，两人脸上都洋溢着傻乎乎的笑容。其中一个看起来是年轻版的学长，另一个人则长的高高胖胖的。
这张照片的名字是：逐王战队_1。
有1还有2吗？高峰赶紧在每个磁盘都搜索“逐王战队”关键字。
最后，他找到了大大小小的东西，有些是照片，有些是密密麻麻的文档，写着逐王战队的活动安排，还有一些是逐王战队的获奖记录。
他心跳的很快，大脑中闪过几种可能性。
第一，学长就是逐王战队的人，只是隐瞒了这个事实。
第二，学长以前是逐王战队的人，但是现在离开了。
第三，学长是逐王战队的狂热粉丝。
突然，他听到了学长转门把手的声音。他赶紧关掉搜索界面，打开了浏览器，假装在认真读题。
李向南也知道看着别人写代码别人自己也不自在，就把水果端进去就离开了。
书房里，高峰仍然在思考学长的真实身份。他发现自己最惶恐的，就是发现学长身份暴露后就会离开他们。毕竟，参加过国家级比赛的人，怎么会闲着没事一直指导他们几个纯新人呢？
他想了很多。一开始，他纯粹是听说“学习计算机可以学到很多数学知识”才准备学编程，同时他也是萌新战队学的最好的一个，他也习惯了被大家当作最厉害的那个人称赞。
后来，这个学长突然就被以“大佬”的身份被拉进了群，面对这样一个完全不认识的“大佬”，他心里确实不太开心，所以出了几道题想噎一噎他。
没想到，这个学长真的是一个很负责的人：他可以毫无条件地帮助新认识的学弟学妹，就为了能提高他们几个的水平。
他想，学长确实是一个很喜欢编程的人，这和自己完全不一样。
一个刻苦，一个只是打发时间。
同时，他也觉得，这也是学长的魅力所在。这样的学长，自己队拥有就可以了，怎么能让别的队伍捡到便宜呢？
高峰最后平复了一下心情，下了一个决定。
他要用各种手段把学长留在萌新战队，不管他到底是什么身份！
想到这里，高峰又开始安心打题了，准备先把自己培养成一个强者。等到自己的实力超过逐王战队那几个人，学长自然就是自己队的了。
作者有话说
第5章 第五章 第二次培训：贪心算法
，还差 