0%

生日蛋糕问题是一道很典型的题目,让我对剪枝优化有了更深刻的理解。

这道题的剪枝优化应该从三个方面入手,搜索方向、体积、表面积。我总结了一下,这三种剪枝很有代表性,搜索方向是搜索技巧上的剪枝;体积上的优化是将解决问题过程中不符合要求的方案的剪枝,如果搜索时发现,从当前的方案继续搜索是不可能搜索出结果的,就可以直接回溯了;而表面积上的优化,是出于对问题结果的分析的剪枝,如果是搜索最优方案的题目,不能搜索出比当前的最优方案更优的方案时,是可以回溯的。

FATE

Problem Description

最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗?

问题描述:

有一种多米诺骨牌是平面的,其正面被分成上、下两个部分,每一部分的表面或者为空,或者被标上1至6个点。现在有一行多米诺骨牌排列在桌面上,如下图: