算法合集之“正难则反–浅谈逆向思维在解题中的应用”.pptVIP

正难则反 —— 浅谈逆向思维在解题中的应用 引入 有一排路灯，一共八盏，均关闭。要求打开其中三盏，没有任意两盏相邻，有多少种不同的方式。 如果直接考虑三盏打开的灯，需要讨论！ 不妨来考虑没有被打开的那些灯。 引入 引入 逆向思维是一种思考问题的方式，它有悖于通常人们的习惯，而正是这一特点，使得许多靠正常思维不能或是难于解决的问题迎刃而解。 例一、Dinner Is Ready [题目描述] M根骨头分给n个孩子，第i个孩子有两个参数Mini和Maxi，表示第i个孩子至少要得到Mini根骨头，至多得到Maxi根骨头。 给出n(0n≤8) , M(0M)以及Mini和Maxi (0≤Mini≤Maxi≤M) 计算有多少种分配方案(骨头不能浪费，必须都分给孩子们） 例一、Dinner Is Ready 例一、Dinner Is Ready 该题模型即求如下方程组的整数解的个数： 例一、Dinner Is Ready 设S为全集，表示满足Xi≥Mini的整数解集。 例一、Dinner Is Ready 例一、Dinner Is Ready 至此，问题已经被解决。 例二、Greedy Path 例二、Greedy Path 例二、Greedy Path 例二、Greedy Path 例二、Greedy Path 例三、Building Towers 例三、Building Towers 例三、Building Towers 例三、Building Towers 例三、Building Towers 逆向动态规划的好处在于： 1)自顶向下的看问题，有“一览众山小”的开阔视野，可以顺利地为如何搜，先搜什么后搜什么，以及如何剪枝等作合理的布局。 2)在类似于本题的计数问题中，可以采用部分记忆化的方法，即只记录那些比较容易被多次有哪些信誉好的足球投注网站到的状态。这样一来，减少了存储的状态量，加快了查询的速度。 例三、Building Towers 让我们来看看逆向动态规划的精彩表现： 总结 总结 * * 绍兴市第一中学 唐文斌 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 要开3盏灯，则有5盏是关闭的 两盏相邻的关闭的灯之间只能插入一盏开着的灯 等价于在六个可选位置中选三个插入开着的灯 所以答案为C(6,3) 逆向思维 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 问题 答案 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 实例： N=3 M=7 Min1=1 , Max1=2 Min2=2 , Max2=4 Min3=3 , Max3=6 1 2 4 1 3 3 2 2 3 3组可行方案 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. X1+X2+X3+…+Xn=M Min1 ≤X1 ≤Max1 Min2 ≤X2 ≤Max2 …… Minn ≤Xn ≤Maxn 对于方程组的简单形式 xxxX1+X2+…+Xn=M xxxXi ≥ 0(1≤i≤n) 我们知道方程解数为C(M+n-1,n-1) 设Yi = Xi + Mini 则方程组变为： Y1+Y2+Y3…+Yn=M-Min1-Min2-…-Minn 0 ≤Y1 ≤Max1