rbbAAA贪心算法经典例题

贪心算法经典例题 在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心算法。 从贪心算法的定义可

贪心算法经典例题 在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去 求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解 方法就是贪心算法。 从贪心算法的定义可以看出,贪心法并不是从整体上考虑问题,它所做出的选 择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法 可以得到最优解。 我们看看下面的例子 例1均分纸牌(NOIP2002tg) [问题描述]有N堆纸牌,编号分别为1,2,…,N。每堆上有若干张,但纸牌 总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编 号为1堆上取的纸牌,只能移到编号为2的堆上;在编号为N的堆上取的纸牌,只 能移到编号为N-1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。 现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。例如 N=4,4堆纸牌数分别为: ①9②8③17④6 移动3次可达到目的: 从③取4张牌放到④(981310)->从③取3张牌放到②(9111010)-> 从②取1张牌放到①(10101010)。 [输入]:键盘输入文件名。 文件格式:N(N堆纸牌,1<=N<=100)