搜索
引入有一排路灯，一共八盏，均关闭。要求打开其中三盏，没有任意两盏相邻，有多少种不同的方式。如果直接考虑三盏打开的灯，需要讨论！不妨来考虑没有被打开的那些灯。引入要开3盏灯，则有5盏是关闭的两盏相邻的关闭的灯之间只能插入一盏开着的灯等价于在六个可选位置中选三个插入开着的灯所以答案为C(6,3)引入逆向思维是一种思考问题的方式，它有悖于通常人们的习惯，而正是这一特点，使得许多靠正常思维不能或是难于解决的问题迎刃而解。问题答案例一、DinnerIsReady[题目描述]M根骨头分给n个孩子，第i个孩子有两个参数Mini和Maxi，表示第i个孩子至少要得到Mini根骨头，至多得到Maxi根骨头。给出n(0n≤8),M(0M)以及Mini和Maxi(0≤Mini≤Maxi≤M)计算有多少种分配方案(骨头不能浪费，必须都分给孩子们）例一、DinnerIsReady实例：N=3M=7Min1=1,Max1=2Min2=2,Max2=4Min3=3,Max3=61241332233组可行方案例一、DinnerIsReady该题模型即求如下方程组的整数解的个数：X1+X2+X3+…+Xn=MMin1≤X1≤Max1Min2≤X2≤Max2……Minn≤Xn≤Maxn对于方程组的简单形式xxxX1+X2+…+Xn=MxxxXi≥0(1≤i≤n)我们知道方程解数为C(M+n-1,n-1)设Yi=Xi+Mini则方程组变为：Y1+Y2+Y3…+Yn=M-Min1-Min2-…-Minn0≤Y1≤Max1-Min10≤Y2≤Max2-Min2……0≤Yn≤Maxn-Minn下界我们可以通过换元得到简单形式但是上界仍然无法解决！例一、DinnerIsReady设S为全集，表示满足Xi≥Mini的整数解集。设Si为S中满足约束条件Xi≤Maxi的整数解集,Si为Si在S中的补集，即满足XiMaxi(Xi≥Maxi+1)|Si|无法计算，但是，|Si|可解！！！那么，我们是否可以通过可解的|Si|从而得到无法计算的|Si|呢？例一、DinnerIsReady于是，我们就得到了：nSSSSAnswer...321n1113121n21...*)1(....)...()...(SSSSSSSSSSSSSnnn例一、DinnerIsReady至此，问题已经被解决。时间复杂度为O(2n*(n+M))在原集合Si的模|Si|不可解的情况下，我们通过可解的|Si|得到了一个基于容斥原理的算法。例二、GreedyPath[题目描述]给定一个有向图G=(V,E)对于e∈E,有参数Ce和Te,分别表示该条边的费用与时间。求一个回路，使得回路中费用总和与时间总和的比值最大。例二、GreedyPath题目是求一条回路，但不是边权和最大或者最小，不能直接使用经典算法，似乎无从下手。我们的目标是找一条回路C=(V’,E’),使得F(C)最大：'')(EeeEeeTCCF例二、GreedyPath0*)(**EeeEeeTCFC设S为G中所有回路组成的集合。假定C*=(V*,E*)∈S就是我们要求的最优回路***)(EeeEeeTCCF定义函数O(t):'')','(*max)(EeeEeeSEVCTtCtO例二、GreedyPath我们做一个猜想：如果有o(t*)=0，也就是存在C*=(V*,E*)∈S满足：***EeeEeeTCt我们认为C*就是最优回路！证明：如果存在另一条回路C1=(V1,E1)∈S更优则*)()(*0*11111toTtCtTCtEeeEeeEeeEee与O(t*)=0矛盾例二、GreedyPath更进一步，可以发现：如果t*是最优答案，则存在：*0)(*0)(*0)(tttotttottto根据该性质，便得到了算法：我们只要从一个包含t*的区间(tl,th)开始，不断地二分，计算o((tl+th)/2)，得到新的上下界，直到达到精度要求。时间复杂度为O(lgK*N3)例三、BuildingTowers[题目描述]用N块积木来搭建H层的塔(不一定要用完所有的积木)要求相邻的两层积木数量相差为1最底层积木数量为M(N≤32767,H≤60,M≤10)任务1：可以搭建成多少种不同的塔?任务2：用H个整数从底到顶表示一个塔的结构，问字典序第K小的塔是什么？(H=6,M=2,N=13)例三、BuildingTowers动态规划算法用F[i,j,k]表示当前层有i块砖，还剩下j层，可用的砖块数量为k的方案总数动态规划方程：F[i,j,k]=F[i+1,j+1,k-i]+F[i-1,j+1,k-i]边界条件:F[M,H,N]=1,其他为０例三、BuildingTowers容易看出，这个动态规划方程一共涉及了N*M*K个状态，最大约为60*70*2400=10M。如果每个状态用一个double来保存信息，则至少需要80M的内存不论是时间复杂度，还是空间复杂度，都让人难以接受。例三、BuildingTowers将规划的顺序作一个反转，有什么好处呢？记忆化因子自顶向下的搜索算法逆向动态规划自底向上的动态规划算法例三、BuildingTowers逆向动态规划的好处在于：1)自顶向下的看问题，有“一览众山小”的开阔视野，可以顺利地为如何搜，先搜什么后搜什么，以及如何剪枝等作合理的布局。2)在类似于本题的计数问题中，可以采用部分记忆化的方法，即只记录那些比较容易被多次搜索到的状态。这样一来，减少了存储的状态量，加快了查询的速度。例三、BuildingTowers让我们来看看逆向动态规划的精彩表现：NHM正向动态规划所需要处理的状态量逆向动态规划中存储的状态量正逆向动态规划状态数比值1000401012000003055392.801500501026250005371488.741200601028800004987557.741500601036000003801894.69总结例一补集转化思想例二参变量法例三逆向动态规划总结以退为进避其锋芒攻其软肋打破思维定势反弹琵琶成新曲ThankYou!