其余的条件全靠自己判断
回6，7楼 消耗最少的人不一定能带足够多的粮食供2N天用，每个人不一定都带自己能带的最多粮食 也就是说一定要考虑协作！
回9楼 必须满足出发N天后有人到达山顶，出发2N天后无人滞留山上。这样，只能第一天出发。

原文链接：http://www.mydrs.org/program/list.asp?id=111

问题

　　攀登某高山，假定上下山速度相等。从山脚到顶峰有N天的路程（N<10）。某登山队有P名队员，每人可负载最大给养量和每天消耗的给养量各不相同，只要在N天内全队有一个队员登上顶峰，并且在2N天内所有参加登山的队员安全返
回山脚，就算此次登山成功。登山规则：参加登山的队员同时同地出发，在山上不许停留；给养可以相互补给，但必须由登山队员随身携带。编程要求：用键盘输入天数N，队员数P，队员按1，2，…，P编号。然后按编号输入每个队员的可
负载最大给养量和每天的消耗的给养量（给养单位为公斤）。输出两个登山计划。 其一是，在参加登山的队员数最少的情况下消耗总给养量尽可能少的计划；其二是，消耗给养最少时的计划。登山计划的内容是：有多少队员参加登山，在出发时每人各带多少天的给养，每人各在出发几天后返回。
　　　　　　　　　　　

题义分析

　　本题给出了P个登山队员每人的最大给养负重和每天的消耗，要求在保证至少一人登顶且所有人员安全返回的情况下，确定两个登山方案，使得：

　　1． 参加登山人数最少，消耗给养尽可能少

　　2． 消耗给养最少。注意每个队员的"能力"是不同的，包括负重和消耗。显然，负重越大，消耗越少的队员，越有利于登山。　　　　　　　　　　　　　　

算法分析 　

　 　之所以要从P个队员中选择若干人登山，是因为每个队员的负重能力有限，不可能背负2N天所需的所有给养，所以在登顶过程中，不但要吃自己的给养，也要吃他人的给养，才能保证登顶并安全返回。

　　 所以我们确定一个方案时关心以下内容：　　　　　　　　　　　　　　　　　　　

　　 1． 由谁完成登顶任务。根据题意，只要一个人登顶即可，我们假设是编号为Final的登山队员。那么除了Final之外，其他人都不必登顶（否则就"浪费"了）。通常，Final的最大负重无法满足自身2N天的要求，在登山过程中要吃他人的给养。　　

　　 2． 队员之间的如何相互支持。　　　　　　　　　　　　　　　　　　　　　　

　　 3． 除Final以外的队员如何在合适的时间返回。 　　　　　　　　　　　　　　　　

　　 4． 各队员分别在出发时带多少给养。 　　　　　　　　　　　　　　　　　　　　　

登山过程 　　

　　 登山的过程比较复杂，牵涉到队员携带的给养、返程时间、互相支援等方方面面， 这些都是不确定的因素，如果从起始点开始考虑，有千头万绪无从下手的感觉。例如确定各队员返程日期，若某队员返程早，可以节省给养，但余下的队员可能因得不到支持而无法登顶；反之，如果该队员太迟返程，则可能导致总给养耗费过大或无给养下山等问题。

　　 因此，我们考虑用倒推的方法，从"登顶"这一目的出发，逐一确定登山的过程。 　　

　　 由于只有Final一人登顶，所以在登顶以后他必须吃自己的给养下山。同时，在此以 前他也应当尽量先吃他人的给养--这样意味着他人可以尽早下山，减少花在他人身上的给养。如图1，假设Final在登山开始后第X1天开始吃自己的给养，则至少一名队员要"陪"Final到第
X1-1天，以供给Final。那么需要多少名队员到X1-1天开始返程呢？一名队员就够了，因为除Final之外的队员越早返程，所消耗的总给养越少。假设这名队员是T1。图1是T1支持Final的情况。　　
　　　　　　　　　　　　　　　　　　

　　其中X2至X1一段T1和Final的给养由T1单独提供。所以T1的给养用在X2X1至起点一段， Final的给养用在X1至终点一段。图1中粗线部分，T1和Final的给养"尚无着落"。我们考虑让别的登山队员来保证他们能顺利到达X2（实际上，从X2以后，其他队员都可以回山脚，
T1与Final继续前进）。假设由T2来提供一部分的给养。图2表示了T2的给养分配状况。 由于起点至X3一段3人的给养还需要他人支援（如果这一段>0）。那么我们继续引入T3、T4…
直到不需要额外的支援，即某一个XK和起点重合。 　　

　　 以上的分析是通过倒推的形式确定登山的过程，现在我们来看看从登山的开始到结束的全过程： （图2）　　

　　 假设共由M+1人参加登山。

　　 在起点至XM段，TM负责全队的给养，然后在XM处，返程过程中吃自己的给养。 　　

　　 在XM至XM-1段，TM-1负责继续登山的队员（全队除去TM）的给养，然后在XM-1处返程，返程过程中吃自己的给养。 　　

　　 在XI+1至XI段，TI负责继续登山队员的给养，然后在XI处返程，返程过程中吃自己的给养。

　　 从X1处开始，只有Final一人继续登山，登顶后返程。这一过程Final吃自己的给养。

　　 登山成功。

确定人选

　　如图3示，登山过程中的Final、T1、T2等队员需要从已知的P个登山队员中选择。由于登山的过程已经确定，那么只要确定具体人选和担负的"职责"，就可以确定所需给养总量。
img src="pic/0003.gif" width="235" height="201"border="0">
　　确定人选的过程可以用枚举的方法实现，比如用深度优先搜索。在搜索过程中，可以将两个任务分开搜索。因为任务一的最优解生成趋势是人数逐渐变少，费用逐渐增多，而任务二的最优解生成趋势是人数逐渐变多，费用逐渐减少（见图3）。分别编写两个搜索两种任务的子程序，可以有效地进行较为有效的截枝。

总结 　　

　　本题解题的过程是一个倒推的过程。确定登山的过程是解题的关键，这一过程紧紧抓住"登顶"这一目的，使得目标明确，思路比较清晰。

作者：羌云云
来源：曙光奥赛
时间：2001-07-13

豁然开朗...

了解...