算法经典“钓鱼”问题详解基于贪⼼算法C语⾔描述
算法经典“钓鱼”问题详解基于贪⼼算法
初始条件
在⼀条⽔平路边，有 n 2 ≤ n ≤ 25个钓鱼池，从左到右编号为1、2、3、……、n。⼩明有H1 ≤ H ≤ 16个⼩时的空余时间，他希望⽤这些时间钓到尽量多的鱼。他从池塘1出发向池塘n⾛，有选择地在⼀些池塘边停留⼀定的时间钓鱼，最后在某⼀个池边结束钓鱼。⼩明测出从第i 个池塘到第i+1个池塘需要⾛5T i分钟的路。还测出在第i个池边停留，第⼀个5分钟可以钓到鱼量F i，以后再每钓5分钟鱼，鱼量减少D i。假设没有其他⼈钓鱼，也没有其它因素影响⼩明钓到期望数量的鱼。
要求完成的主要任务
基本要求
请编程求出能钓最多鱼的⽅案。很显然，在分析本题数据前你需要⾸先构造出数据。
究竟在应该每个池塘停留多久？这正是需要你通过算法进⾏计算的。上述表格的具体数值可以通过随机函数⽣成，但你得注意不要让⾸个5分钟可以钓到的鱼量和每隔五分钟减少的鱼量的差值太过离谱。
另外，由于输出内容较多，⼀屏往往显⽰不完，所以输出结果必须保存到⽂本⽂件中以便单独查看。
输⼊输出
总过有多少个池塘，以及⼩明总共有多少时间，可以在程序运⾏时从键盘输⼊。上述表格数据应提供两种⽅式输⼊：1)通过随机函数⽣成，且可以⼆进制形式保存到⽤于输⼊的⽂件中；2)通过输⼊⽂件读⼊。
经过计算以后的输出格式（⽰例）为：见1.4 数据输出的形式
实现提⽰
从题⽬可以看出，⼩明每做⼀件事情所花费的时间都是5分钟为⼀个基本单位，因此可以直接⽤5分钟作为⼀个基本计时单位来简化处理⽅式。尽管各个池塘的可钓鱼量并不均等，但我们可以假定这些池塘是按照鱼量从⼤到⼩排列的（想想看为什么？），然后枚举这些池塘每⼀个可操作时段的理论收获值，并通过贪⼼算法来计算最⼤可钓鱼量。亦即可以每次选⼀个鱼最多的池塘钓⼀次鱼，对于每个池塘来说，由于在任何时候鱼的数⽬只和⼩明在该池塘钓鱼的时长有关，⽽和钓鱼的总时长⽆关，所以这个策略⼀定是最优的。问题只在于，每个池塘是否应该⼀直钓到⽆鱼可钓为⽌？这就是需要你动脑筋去思考的问题了。如果这个问题你能到⼀条清晰的思路来解决，将对你的编程思维模式起到极好的锻炼作⽤。
1. 需求分析
1.1 题意解析
依题意，这是⼀个使⽤贪⼼算法求最值的问题，但它⼜不是简单的到鱼最多的池塘然后去钓鱼的问题。对于本题⽽⾔，题⽬主⼈公的时间有限，每次钓鱼会消耗时间，主⼈公在池塘间移动也会消耗时间，作者需要在有限的时间内，帮助主⼈公获取最多的鱼。另外，池塘也是动态的，在主⼈公钓鱼后，下⼀次钓鱼的数量会减少。本课题转换成算法导向后的表述形式为：
对于有n条记录的顺序表，已知每条记录的索引值i、到达鱼塘所需时间ti、钓五分钟鱼可获得的鱼量fi、每次钓鱼后鱼量减少量di和⼩明拥有的时间T⼩时。⼩明每钓⼀次鱼会消耗5分钟，同时该池塘fi递减为fi-di。设⼩明最远⾛到第m个池塘m<n，⼀共钓了c次鱼，需要求在 情况下，得总收获鱼量S最⼤值。
1.2 数据的输⼊形式
根据题⽬要求，数据需要从⼆进制⽂件中读⼊或者由程序随机⽣成。但仍然需要保留⼈⼯由键盘输⼊的输⼊模式，以⽣成测试⽤的⼆进制⽂件，便于后期测试与调试。
1.3 数据输⼊的范围
此题中的数据需要输⼊的有：钓鱼总时间、池塘个数以及每个池塘对应的信息。依题意，钓鱼总时间为H⼩时，1 ≤ H ≤ 16；池塘个数n 个，2 ≤ n ≤ 25。
具体到每⼀个池塘的数据，题⽬要求不要让⾸个5分钟可以钓到的鱼量f和每隔五分钟减少的鱼量d的差值太过离谱。根据分析，对它们进⾏d不得⾼于f的1/2，并且不得少于⼗分之⼀，即⌊f/10⌋ < d < ⌊f/2⌋的约束是⽐较合理。另外，题⽬还未规定每个池塘具体参数的数据，结合客观实际的钓鱼场景，现设定5≤ t ≤ 40（分钟），3 ≤ f ≤ 40，1 ≤ d ≤ 20。
1.4 数据输出的形式
根据题⽬要求的输出格式，主要以⽂本的形式分别在终端和⽂件中输出，输出中包括题⽬主⼈公的钓鱼时间，池塘的总数和各池塘的具体参数，以及在每⼀个池塘中钓鱼的具体过程：前往某个池塘花了多久，停了多长时间，每五分钟钓了多少的鱼还有获得鱼的总量，最后还要有路途耗时、钓鱼耗时、总计耗时和获得鱼量的总数统计信息。该输出⽅式直观清晰，数据量⼤，不仅能清晰的反映钓鱼的过程和结果，还便于程序的调试。具体如下：
⼩明拥有的时间：H⼩时，合计60H分钟
池塘总数：n
各池塘参数：
池塘编号⾏程时间⾸次鱼量递减鱼量
1    t1    f1    d1
2    t2    f2    d2
……
具体过程：
抵达1号池塘：花费时间t1分钟，停留时间c1分钟，获得鱼量f1+(f1-d1)+(f1-2*d1)+…
抵达2号池塘：花费时间t2分钟，停留时间c2分钟，获得鱼量f2+…
抵达3号池塘：花费时间t3分钟，停留时间c3分钟，获得鱼量f3+(f3-d3)+f3 mod d3=…
……
最终统计结果，⼩明路途花费合计xxx分钟，在各池塘停留合计yyy分钟，总计耗时zzz分钟，获得鱼量合计www条。
虽然该输出由以上的优点，但在c语⾔程序实现中略显⿇烦。特别是在每⼀个池塘的具体过程的输出中，不同的钓鱼情况会有不同的输出：没有停留的池塘，直接输出0；停留了⼀次的池塘，直接输出fi；停留了多次的池塘，需要根据停留次数输出(fi-c*di)，且第⼀次是fi，第⼆次是(fi-di)，最后⼀次是(fi-c*di)或者fi mod di的值，并且在最后带上“=该池塘收获总量”。
1.5 程序⽬标
（1）通过⽂件或者随机的形式获取池塘和⼩明的数据；
（2）⼈⼯或者随机⽣成池塘数据并保存在⼆进制⽂件当中；
（3）将获得的数据正确地计算为正确并带有过程的结果；
（4）显⽰从⽂件读取或者随机⽣成的数据；
（5）显⽰每⼀步详细的计算过程；
（6）显⽰最终的结果；
（7）在输⼊错误或⾮法时做出正确的响应并提供重新输⼊的机会；
1.6 测试数据
（1）池塘个数：n，2 ≤ n ≤ 25，特别是2与25。
（2）空闲时间：H，1 ≤ H ≤ 16，特别是1。
（3）具体池塘参数：5≤ t ≤ 40，3 ≤ f ≤ 40，1 ≤ d ≤ 20，特别是d = f/2和d = f/10。
（4）每个池塘参数相同的情况。
（5）空闲时间⼤于钓完所有鱼的情况，空闲时间刚好够钓完所有鱼的情况，使⽤不同时间钓鱼结果相同的情况，⼀般情况。
（6）需要⼈⼯输⼊时不合法数据。
2. 概要设计
2.1 算法思路
由题⽬描述，⼩明所有的⾏为都是以5分钟为单位进⾏，故在分析以及程序实现的过程中将⼩时、分钟等时间简化为每五分钟为⼀个单位的形式来表达。
⼩明钓鱼只有⼀条路，只能在该条路上前进后退，⽽每个池塘每五分钟可获得鱼的数量与⼩明在哪以及从哪来⽆关，且后退消耗的时间必将导致钓鱼的时间减少。故⽆需考虑⼩明钓鱼时是否会回头选择池塘钓鱼，只需要考虑在每个池塘停留的时间。根据题⽬提⽰，使⽤贪⼼算法，计算时直接考虑在当前情况下可钓鱼的最多的池塘，进⾏⼀次钓鱼并记录收情况和鱼量变化情况，然后根据鱼量重新排序池塘，再去鱼最多的池塘钓鱼，重复以上过程，直⾄鱼钓完或者是时间⽤完停⽌。
但问题出现了，如何确定⼩明最远要去到⼏号池塘呢？这就需要通过循环的⽅式，从每个池塘都钓鱼开始计算，计算到只在⼀个池塘中钓鱼的情况，然后通过⽐较，确定钓鱼数量最多，以及⽤时最少的情况输出。
具体的算法思路是：
1）将n个池塘根据⾸次鱼量由⼤到⼩排序；
2）将⼩明空闲时间扣除掉前往这些池塘的路途时间之和；
3）⼩明“前往”鱼最多的池塘钓鱼，该池塘的⾸次鱼量减掉递减鱼量，⼩明的空闲时间扣除此次钓鱼的时间；
4）重新根据⾸次鱼量排序池塘；
5）重复3）⾄4）步，直⾄鱼钓完或者是时间⽤完，记录下钓鱼过程、钓鱼⽤时以及获得的鱼的数量；
6）恢复所有池塘到初始状态，剔除最远的⼀个池塘，重复1）⾄5）步，直⾄计算到只剩⼀个池塘；
7）⽐较不同池塘数量情况下的钓鱼⽤时和获得鱼量，选择⽤时最短、鱼量最多的情况保存输出。
2.2 技术路线
数据存储
池塘在⼀条⽔平路边，不会有池塘的删除或者插⼊，⾮常适合使⽤顺序表，C语⾔中的数组来存储。但在上述的算法中，涉及到对池塘排序，不可使⽤池塘存储时的数组索引来标识池塘，需要另外增加⼀个属性。
每⼀个池塘有⾏程时间、⾸次鱼量、递减鱼量三个重要属性，这些在C语⾔中可以使⽤int型来存储。另外，为了唯⼀地标识每⼀个池塘，池塘还需要加⼀个编号，也使⽤int型存储。综上，在本题中，⼀个池塘在C语⾔中使⽤⼀个由四个int组成的结构体存储。
数据初始化
本题中数据来源有随机⽣成，为了降低程序的复杂性，初始化池塘数据⼀律使⽤随机⽣成，随机出来的数据符合题⽬要求和以上的规定。⼈⼯输⼊数据时直接覆盖随机⽣成的数据，不再单独初始化。
排序
以上算法中涉及到两次排序，⼀是在钓鱼前，根据⾸次鱼量排序，⼆是恢复初始的池塘状态，即根据编号排序。根据鱼量排序时，不妨设想以下情景：⼩明只剩⼀次钓鱼的机会，有两个池塘都有着最⼤的相同的⾸次鱼量，如果⼩明去更远的地⽅钓鱼，就意味着将鱼送回家时需要花费更多的⼒⽓，不太划算。因此，在进⾏根据鱼量的排序时，对排序算法的稳定性有要求，故使⽤冒泡排序的⽅法。但在根据编号排序时，由于编号不可能相同，因此就没必要要求排序算法的稳定性，使⽤快速排序。当然，本题需要排序数据量最⾼也不到30，⽆论是冒泡排序还是快速排序，虽然时间复杂度上不同，但在实际程序中的时间表现差别不⼤。
钓鱼过程记录
由于钓鱼过程需要在程序中多次计算然后⽐较，不适合与池塘数据绑定在⼀个结构体中。⽽所谓钓鱼过程，经分析，可以仅仅由某次过程所达最远的池塘编号和在每个池塘停留的时间组成，即可完整的表⽰⼀次钓鱼的过程。因此，使⽤⼀个辅助数组来存储每个池塘的停留时间。其中，数组的索引对应池塘的编号，所存储的值就是停留的时间单位。
模块设定
在上述算法中，多次涉及到给定范围随机数⽣成、给定关键字排序，以及在不同条件下都要进⾏的内存分配、“钓鱼”过程等。另外，由于此题的输出较为复杂，输出将为单独的模块。故本程序将设有获取时间、获取给定范围随机数、输出池塘数据、⽤户提⽰界⾯、池塘数组⽣成、钓鱼、输出钓鱼结果、排序等模块。
调试⼿段
⼀是通过在程序中使⽤打断点等⼿段，观察其中间数据以及内部数据的变化实现代码调试与优化。⼆是通过程序的随机数据⽣成，让程序多次完成完整的计算过程并输出结果，因为此题输出完整、详细，可以通过观察输出来判断是否有错误，并结合⼀的⽅法调试。三是⼈⼯设计若⼲简单⽽⼜处于临界值部分的数据，进⾏⼿⼯计算后通过程序的⼈⼯数据⽣成功能输⼊到程序中计算，⽐较计算结果来判断运⾏正误，进⽽调试。
程序运⾏模式
程序利⽤C语⾔中goto语句实现循环的运⾏模式，避免⽤户反复启⽤程序不⽅便。在程序开始时，⽤户可以选择若⼲个程序功能，每次运⾏完后回到功能提⽰处运⾏，直⾄⽤户主动退出。
2.3 抽象数据类型
ADT 池塘 Pond {
数据对象：pond是⼀个存储有⼀个池塘所有数据的结构体，该结构体由四个int型数据构成。
数据关系：集合结构，每个pond必有4个int。
基本操作：
initRandomPond()
操作结果：随机⽣成⼀个池塘，数据范围为题⽬规定。
swapPond(Pond1, Pond2)
初始条件：两个池塘数据存在。
操作结果：交换两个池塘的数据。
}
ADT 池塘顺序表 Ponds {
数据对象：Ponds是⼀组数据池塘的集合。
数据关系：线性结构，其中必存在唯⼀的⼀个“第⼀池塘”，必存在唯⼀的⼀个 “最后池塘”，除最后⼀个池塘之外，均有唯⼀的后继，除第⼀个池塘之外，均有唯⼀的前驱。
基本操作：
pondsArry(length, ponds)
操作结果：随机初始化⼀个长为length的ponds顺序表。
printPonds(ponds, len, file)
初始条件：⽂件与ponds存在。
操作结果：在终端格式化输出前len个池塘的数据，并格式化写⼊到file⽂件中。
sumRouteTime(ponds, amount)
初始条件：ponds存在。
操作结果：计算ponds中到达第amount个池塘所需时间。
copyArry(Ponds1, Ponds2, length)
初始条件：(Ponds1存在。
操作结果：将Ponds1中前length池塘的数据复制到Ponds2中。
sortPondsByFish(ponds, amount)
初始条件：ponds存在。
操作结果：ponds中前amount个池塘按⾸次鱼量从⼤到⼩存储。
sortPondsByIndex(ponds, amount)
初始条件：ponds存在。
操作结果：ponds中前amount个池塘按编号从⼩到⼤存储。
goFishing(freeTime, ponds, pondAmount)
c语言的冒泡排序算法
初始条件：ponds存在。
操作结果：计算在freeTime下，⼩明在前pondAmount个池塘中钓鱼的过程与获得鱼的数量。
fishingRecord(freeTime, ponds, process)
初始条件：ponds存在。
操作结果：根据process和freeTime输出⼩明在ponds钓鱼过程。
}
2.4 主程序流程
程序启动后，有五个选项，⽤户选择具体功能运⾏，运⾏完成后回到功能选择界⾯，直⾄⽤户主动结束运⾏。具体过程如图。
具体的，计算钓鱼过程模块的描述详见2.1算法思路中的具体思路，这⾥给出其流程图。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。