贪心算法的思想 贪心算法的基本思想是找出整体当中每个小的局部的最优解,并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质: 1.整体的最优解可以通过局部的最优解来求出; 2.一个整体能够被分为多个局部,并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。  在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。 特别注意:&n…

2017年5月13日 0条评论 3点热度 阅读全文

贪心算法的思想 贪心算法的基本思想是找出整体当中每个小的局部的最优解,并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质: 1.整体的最优解可以通过局部的最优解来求出; 2.一个整体能够被分为多个局部,并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。  在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。 特别注意:&n…

2017年5月13日 0条评论 2点热度 阅读全文

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines…

2014年11月16日 0条评论 1点热度 阅读全文

     1. 田忌赛马  典型的贪心算法~~自己木有考虑到贪心的第二步导致wa了好多次 算法分析  Problem Description: 给出2N组数据,分别表示田忌和齐威王的N匹马的速度,没进行一场比赛(每组数据共N场场赛),若能分出胜负,则输的一方要给赢的一方200Y¥(银元),求田忌以怎样的策略才能赚取最多的老婆本。 Solution:这题有多种解体思路,DP,二分图最大匹配算法等,这里给出的是比较容易理解的贪心算法,具体思路如下: 先将田忌跟…

2014年7月31日 0条评论 2点热度 阅读全文

     1. 田忌赛马  典型的贪心算法~~自己木有考虑到贪心的第二步导致wa了好多次 算法分析  Problem Description: 给出2N组数据,分别表示田忌和齐威王的N匹马的速度,没进行一场比赛(每组数据共N场场赛),若能分出胜负,则输的一方要给赢的一方200Y¥(银元),求田忌以怎样的策略才能赚取最多的老婆本。 Solution:这题有多种解体思路,DP,二分图最大匹配算法等,这里给出的是比较容易理解的贪心算法,具体思路如下: 先将田忌跟…

2014年7月31日 0条评论 2点热度 阅读全文