贪心算法与动态规划

贪心算法与动态规划贪心算法与动态规划贪心算法（ Greedy Algorithm ）贪心法的基本思路：  ——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。贪心算法的基本步骤  1 、从问题的某个初始解出发。  2 、采用循...

贪心算法与动态规划贪心算法（ Greedy Algorithm ）贪心法的基本思路：  ——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。贪心算法的基本步骤  1 、从问题的某个初始解出发。  2 、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。  3 、将所有部分解综合起来，得到问题的最终解。活动安排问题  活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。贪心算法使得尽可能多的活动能兼容地使用公共资源  设待安排的 11 个活动的开始时间和结束时间按结束时间的非减序排列如下： 1413121110987654f[i] 122886535031S[i] 1110987654321i  若被检查的活动 i 的开始时间 Si 小于最近选择的活动 j 的结束时间 fi ，则不选择活动 i ，否则选择活动 i 加入集合 A 中。  可以证明，如果在可能的事件 a1=f[j]) { a[i]=true; j=i; count++; } else a[i]=false; } return count; } FOJ 1111 Radar Installation •给出雷达的扫描半径 R与孤岛的个数 N与坐标， •求最小要用几个这样的雷达。  枚举每一个孤岛  求出其与 X 轴的交点  dx = sqrt(r * r - y * y);  x_min = x - dx;  x_max = x + dx;  Nlog(n) 排序  判断其它点也 X 轴的交点是否在  [x_min,x_max] 范围内 , 或包含相关题目  1574 一食堂宣传栏  1230 区间相交问题 FOJ 1106 Sum of Factorials  问一个数能否由相应的阶乖的和组合而成  列表 {1,1,2,6,24,120,720,5040,40320,362880};  将 N 尝试性的减去表中的数，为零则 YES ，否则为 NO  证明？ FOJ 1085 Work Reduction  给出初始时的工作量 n ，结束时剩下的工作量 m ，给出可以完成这些工作量的公司，这些公司的收费方式有两种， A 一种是减少一个单位的的工作量，每减少一单位工作量花费 a ， B 一种是减少一半单位的工作量，总的花费为 b ，问，分别由这些公司完成的最小的费用。  当前工作量 cur_n 的一半小于 m 时，只能用 A 方法  否则  (Cur_n-cur_n/2)*a > b 时，选择 B 方法 选择 A 方法  如此循环  N <= 100000 如此 log(N) 的复杂度很好的避免了用其它方法可能出现的 TLE 1150Peter's smokes  皮特有 n 根烟 , 有一个兑换数 k.皮特每抽一根烟都把烟头留着 ,直到足够 k 个烟头时 , 就可以换一根新烟抽 . 要编写一个程序 , 输入 n,k, 算出皮特最多能抽多少烟 .  sum = n;  while (n / k)  {  sum += n / k;  n = n / k + n % k;  } 1672Minimum Adjacent Value • The minimum adjacent value is the minimum absolute value |a - b| of the two different elements a and b in the array.  If the N elements are all the same, just output the absolute value of the element.  Nlog(N) 排序  求相邻的两个数的差的绝对值 ,  O(N) 扫描求出最小值  It is guaranteed that the element in the array will fit within a 32-bit signed integer.  |a-b| 超过 32 位整型  64 位整型 Long long  若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！  1316Tian Ji -- The Horse Racing  1541Exploration  1505Minimum value 动态规划（ Dynamic Programming ） • 动态规划算法的基本要素 • （ 1 ）最优子结构性质 • （ 2 ）重叠子问题性质 • 掌握设计动态规划算法的步骤。 • (1)找出最优解的性质，并刻划其结构特征。 • (2)递归地定义最优值。（写出动态规划方程）； • (3) 以自底向上的方式计算出最优值。 • (4) 根据计算最优值时得到的信息，构造最优解。 FOJ1004 Number Triangle  求人从顶端到底部 , 每次只能向左下右下走 , 最多能取得的值 . 数据规模 : 行数 1<=R<=1000 数塔中数值 0..100 如图最优解为 [ 7-3-8-7-5 ]=30  状态表示用 a[i][j] 表示第 i 行第 j 列的值。用 F(i,j) 表示第 i 行第 j 列走到底部所能取得的最大值。而 F(1,1) 就是题目所求的答案。搜索源代码  #include  const int M=1000+5;  int a[M][M],n;  inline int max(int x,int y){ return x  const int M=1000+5;  int f[M][M],a[M][M];  inline int max(int x,int y){ return x=1;i--)  for(j=1;j<=i;j++)  f[i][j]=a[i][j]+max(f[i+1][j],f[i+1][j+1]);  printf("%d\n",f[1][1]);  }  return 0;  } FOJ1320 Ones  给一个整数 n ，要你找一个值为 n 的表达式，这个表达式只有 1 + * ( ) 够成。并且 1 不能连续，比如 11+1 就不合法。  输入 n,(1<=n<=10000)  输出最少需要多少个 1才能构成表达式。  样例： n=2=1+1 ans=2  n=10=(1+1)*(1+1+1+1+1) ans=7 Ones  让 f[i] 表示最少数量的 1 能够表示 i 。  add: f[i]=f[j]+f[i-j] 0 规定每次只能选取相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。求最少的得分。例如： 3堆石子 2 5 1 合并方案一 : [2 5 1]->[7 1]->[8] 分数 7+8=15 合并方案二 : [2 5 1]->[2 6]->[8] 分数 6+8=14 FOJ1319 Blocks of Stones  状态表示：  用 a[i] 表示初始时每堆石子的个数。  用 s[i] 表示初始时从第 1堆到第 i堆石子的总和。  用 f[i][j](i<=j) 表示从第 i堆合并到第 j堆的最小分数。 f[i][j]=min{f[i,k-1]+f[k,j]}+w[i,j];  w[i][j]=sum{a[i]…a[j]}=s[j]-s[i-1];  这样枚举是 n^3 的。最长公共子序列问题 LCS  最长公共子序列问题也有最优子结构性质，因为我们有如下定理：  定理 : LCS 的最优子结构性质  设序列 X= 和 Y= 的一个最长公共子序列 Z= ，则：  若 xm=yn ，则 zk=xm=yn且 Zk-1 是 Xm-1 和 Yn-1 的最长公共子序列；  若 xm≠yn且 zk≠xm ，则 Z 是 Xm-1 和 Y 的最长公共子序列；  若 xm≠yn且 zk≠yn ，则 Z 是 X 和 Yn-1 的最长公共子序列。  其中 Xm-1= ， Yn-1= ， Zk-1= 。  由最长公共子序列问题的最优子结构性质可知，要找出 X= 和 Y= 的最长公共子序列，可按以下方式递归地进行：  当 xm=yn 时，找出 Xm-1 和 Yn-1 的最长公共子序列，  然后在其尾部加上 xm(=yn) 即可得 X 和 Y 的一个最长公共子序列。  当 xm≠yn 时，必须解两个子问题，  即找出 Xm-1 和 Y 的一个最长公共子序列及  X 和 Yn-1 的一个最长公共子序列。  这两个公共子序列中较长者即为 X 和 Y 的一个最长公共子序列。  我们来建立子问题的最优值的递归关系。用 c[i,j]记录序列 Xi 和 Yj 的最长公共子序列的长度。其中 Xi= ， Yj= 。当 i=0 或 j=0 时，空序列是 Xi 和 Yj 的最长公共子序列，故 c[i,j]=0 。其他情况下，  1160Common Subsequence  1502Letter Deletion FOJ1147 Tiling  In how many ways can you tile a 2 x n rectangle by 2 x 1 or 2 x 2 tiles?  Here is a sample tiling of a 2 x 17 rectangle.  Input is a sequence of lines, each line containing an integer number 0 <= n <= 250. For each line of input, output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle.  状态表示： F[n] 表示 2 x n 的走道上铺满 1 x 2 ， 2 x 2 的砖块的方法数量  考虑最后一块砖和最后两块砖的放法，很容易写出 DP状态转移方程。  F[i]=F[i-1]+F[i-2]+F[i-2], 边界： F[0]=F[1]=1; 最后一块 1 x 2竖放 :F[i-1] 最后两块 1 x 2横放 :F[i-2] 最后放一块 2 x 2 的 :F[i-2] 另外： n <= 250 ，需要高精度  1018Maximal Sum  1130Bridging Signals  1340Longest Ordered Subsequence  1392Linear Board Game  1432Coin Changing  1559Count Zeros  1506堆箱子 Thank you Slide 1 Slide 2 Slide 3 Slide 4 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 Slide 18 Slide 19 Slide 20 Slide 21 Slide 22 Slide 23 Slide 24 Slide 25 Slide 26 Slide 27 Slide 28 Slide 29 Slide 30 Slide 31 Slide 32 Slide 33 Slide 34 Slide 35 Slide 36 Slide 37 Slide 38 Slide 39 Slide 40 Slide 41 Slide 42

                    本文档为【贪心算法与动态规划】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

贪心算法与动态规划

你可能还喜欢