贪心算法求解马踏棋盘及POJ1011木棒问题解析.docVIP

SticksTime Limit: 1000MS Memory Limit: 10000K Total Submissions: 58000 Accepted: 12785 DescriptionGeorge took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero. InputThe input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.OutputThe output should contains the smallest possible length of original sticks, one per line. Sample Input95 2 1 5 2 1 5 2 141 2 3 40Sample Output65SourceCentral Europe 1995【原题链接】 /JudgeOnline/problem?id=1011【题意描述】 给出N根小木棒（以下称小棒）的长度Li，已知这N根小木棒原本由若干根长度相同的长木棒（以下称原棒）分解而来。要求出原棒的最小可能长度。【数据范围】 木棒数N=64 任意小棒长度Li=50【题目类型】 这题在网络上被称为经典的深搜题，其中用到的搜索方法和剪枝技巧十分经典。就我做过这题之后的感受来看，的确如此。其中的许多技巧效果非常显著而且在其它搜索题中也经常用到。另外建议大家在做搜索题的时候加上时间测试，以便在调程序的时候观察和比较各项剪枝带来的效率提升。【解题思路】 由小到大枚举所有可能的原棒长度，通过深度优先搜索尝试小棒能否组合成原棒，一旦检验成功则算法结束，当前原棒长度即为最小可能原棒长度。 枚举过程如下，设小棒的总长为SUM，最长小棒长度为MAX，从MAX开始由小到大枚举原棒长度LEN，使得LEN能被SUM整除。然后进行搜索，尝试用所有小棒拼出SUM/LEN根的原棒。搜索过程如下，首先用一数组标USED记某一小棒在当前状态下是否已经被用于组合原棒，另有有两个主要参数表示搜索时的状态，CPL表示已经组合好的原棒数，RES表示当前正在组合的原棒（以下称当前原棒）已组合出的长度。在每一种状态下，尝试所有可能拼接在当前原棒上的未使用的小棒，即将满足USED=FALSE且RES+Li=LEN的小棒接入当前原棒，传递RES的参数RES+Li，若RES+Li=LEN，传递CPL的参数CPL+1,否则，传递CPL，同时令USED=TRUE，然后进行递归，进入下一层搜索。退出下层递归后，将USED重新赋为FALSE。当CPL=SUM/LEN时，返回TRUE，表示搜索成功，一旦下一层递归返回TRUE，当前递归也返回TRUE，不断返回，直到跳出函数调用，表示当前原棒长度为可行解，且为最小，输出。本题的难点在于搜索的方法和剪枝的技巧。本题中用到的主要技巧有： 1. 搜索顺序。首先依据小棒长度进行由大到小的排序，在每一层搜索时首先将长度大的小棒填入当前原棒中。因为当相对长的小棒占据了原棒的大部分空间后能大大减小可行的搜索状态。 2. 利用排序剪枝。在组合同一支原棒的时候，由于检验小棒是否可用的顺序也是由大到小的，因此在检验到一支小棒可用时，如果当前棒还合填满，可能填入当前棒的小棒的长度也不会比现在填入的这支小棒长。因此，增加一个递归参数NEXT表示可能用于组合当前棒的第一支小棒的数组下标。参数传递时，若当前正好拼成一支原棒，NEXT还原回1，否则将NEXT+1传递给下一层递归。 3. 不进行重复搜索。即在某一状态，若将某一长度的小棒填入当前原棒进行搜索无法最终拼出所有原棒，则对于当前状态，相同长度的小棒也无法填入当前原棒而得到最终解。因此，在记录小棒长度的数组L中增加一指针用于指向下一个与之长度不同的小棒的数组下标，则搜索时，若某一长度小棒不成功，直接尝试下一个与之长度不同的小棒。 4. 首次只尝试最长的小棒。在第一次组合拼接某一根原棒时，首先放入的是当前最长的小棒，并且，如果当前状态可以完成组合，则该小棒必定要放入之后的某一根原棒中，即假设它放在当前原棒中，若放入后搜索失败，则当前状态必定不可能成功，需要回溯。因此，在RES=0时，若第一次搜索失败，则不断续当前状态的其它搜索。 5.如果当前最长的一支可用小棒L0恰能填满当前正在组合的一支原棒，则如果此次尝试失败，在当前状态下不再做其它尝试，返回上一层递归。因为若当前状态还有可能成功，则当前原棒的剩余长度必定能由另几支更短的小棒L1、L2Ln组合成，且L0必定出现在之后组合的某支原棒之中，则可以将其中的L0替换为L1、L2Ln，而将L0移加当前原棒中，则两种状态等价，因此同样必定失败。因此，在RES+Li=LEN时，若搜索失败，则同样不断续当前状态的其它搜索。6. 判断所剩可用小棒是否足够拼接当前原棒。累加所有小于当前已经尝试的小棒的长度且未使用的小棒，判断是否足够拼接出当前原棒，若不能，则不继续当前搜索。该剪枝效果不很明显，且计算位置放置不佳可能反而降低率效。 【具体代码】#include int n; /小棒总数int len; /当前枚举的原棒长度int parts; /当前组合的原棒数int max; /最长小棒的长度int sum; /所有小棒的总长int tail; /指向尾部长度较小的棒int l642; /存储小棒相关信息bool used64; /标记小棒是否使用void sort() /对小棒进行排序 for (int i=0;in;i+) for (int j=i+1;jn;j+) if (li0lj0) int t=li0; li0=lj0; lj0=t; /给每一个小棒加上指针，指向下一个长度不同的小棒 int i=0; while (in) int j=i+1; while (jn&lj0=li0) j+; for (int k=i;kj;k+) lk1=j; i=j; void initial() /初始化设置所有小棒均未使用 for (int i=0;i=0;i-) sumr+=li0; if (sumrlen) break; tail=i;inline int sumres(int m) /计算下标大于等于m且未使用的小棒总长之和 int sumr=0; for (int i=m;in;i+) if (usedi=false) sumr+=li0; return sumr;bool search(int res,int next,int cpl)/策略2：用next存储当前可用的下一支小棒 /修正参数，当res=len时表示正好拼接成一支原棒 if (res=len) res=0; next=1; cpl+; /当已拼出的原棒为应拼出原棒时，返回TRUE if (cpl=parts) return true; int i=next; while (in) /尝试未使用的小棒 if (usedi=false) /判断接入此小棒是否超出原棒长度 if (res+li0=tail&sumres(i)len-res) break; continue; i+; return false;int main() while (scanf(%d,&n),n!=0) /输入 sum=0; for (int i=0;in;i+) scanf(%d,&li