深度优先遍历 搜索算法 ACM PKU 1011 S

深度优先遍历 搜索算法 ACM PKU 1011 S 深度优先遍历 搜索算法 ACM PKU 1011 S Description 乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示。Input 输入包含多组数据，每组数据包括两行。第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。第二行是截断以后，所得到的各节木棍的长度。在最后一组数据之后，是一个零。Output 为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。Sample Input 95 21 52 15 21 41 23 40 Sample Output 65算法描述【解题思路】由小到大枚举所有可能的原棒长度，通过深度优先搜索尝试小棒能否组合成原棒，一旦检验成功则算法结束，当前原棒长度即为最小可能原棒长度。枚举过程如下，设小棒的总长为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，不断返回，直到跳出 函 关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函 数调用，表示当前原棒长度为可行解，且为最小，输出。本题的难点在于搜索的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 和剪枝的技巧。本题中用到的主要技巧有:1.搜索顺序。首先依据小棒长度进行由大到小 的排序，在每一层搜索时首先将长度大的小棒填入当前原棒中。因为当相对长的小棒占据了原棒的大部分空间后能大大减小可行的搜索状态。2.利用排序剪枝。在组合同一支原棒的时候，由于检验小棒是否可用的顺序也是由大到小的，因此在检验到一支小棒可用时，如果当前棒还合填满，可能填入当前棒的小棒的长度也不会比现在填入的这支小棒长。因此，增加一个递归参数NEXT表示可能用于组合当前棒的第一支小棒的数组下标。参数传递时，若当前正好拼成一支原棒，NEXT还原回1，否则将NEXT+1传递给下一层递归。3.不进行重复搜索。即在某一状态，若将某一长度的小棒填入当前原棒进行搜索无法最终拼出所有原棒，则对于当前状态，相同长度的小棒也无法填入当前原棒而得到最终解。因此，在 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 小棒长度的数组L中增加一指针用于指向下一个与之长度不同的小棒的数组下标，则搜索时，若某一长度小棒不成功，直接尝试下一个与之长度不同的小棒。4.首次只尝试最长的小棒。在第一次组合拼接某一根原棒时，首先放入的是当前最长的小棒，并且，如果当前状态可以完成组合，则该小棒必定要放入之后的某一根原棒中，即假设它放在当前原棒中，若放入后搜索失败，则当前状态必定不可能成功，需要回溯。因此，在RES=0时，若第一次搜索失败，则不断续当前状态的其它搜索。5.如果当前最长的一支可用小棒L'0恰能填满当前正在组合的一支原棒，则如果此次尝试失败，在当前状态下不再做其它尝试，返回上一层递归。因为若当前状态还有可能成功，则当前原棒的剩余长度必定能由另几支更短的小棒L'1、L'2…L'n组合成，且L'0必定出现在之后组合的某支原棒之中，则可以将其中的L'0替换为L'1、L'2…L'n，而将L'0移加当前原棒中，则两种状态等价，因此同样必定失败。因此，在RES+Li=LEN时，若搜索失败，则同样不断续当前状态的其它搜索。6.判断所剩可用小棒是否足够拼接当前原棒。累加所有小于当前已经尝试的小棒的长度且未使用的小棒，判断是否足够拼接出当前原棒，若不能，则不继续当前搜索。该剪枝效果不很明显，且计算位置放置不佳可能反而降低率效。SOURCE:package acm_pku_1011_sticks;import java.util.Scanner;public class Stick{public static int num;public static int ns;public static int length;public static int ok;public static int sticks=new int[64];public static int used=new int[64];//递减排序public static int sort(int bs,int num){for(int i=0;i num;i++){for(int j=i;j num;j++){if(bs[i]bs[j]){int temp=bs[j];bs[j]=bs[i]; bs[i]=temp;}}}return bs;}public static void s(int x){if(x ns){ok=1; System.out.println(length);return;}int j;for(j=0;j num;j++)if(used[j]==0)break;//找到第一根没有使用的木棍used[j]=1;//改变它的使用状态search(x,sticks[j],j);//搜索used[j]=0;//还原它的使用状态}private static void search(int n,int now,int next){if(ok==1)return;if(now==length){//一根木棍还原完s(n+1);//还原下一根 return;}if(next+1 num)return;//总共只有n根短棍for(int i=next+1;i num;i++)if(used[i]==0)if(sticks[i]+now=length){//该木棍加上当前长度小于len used[i]=1;search(n,now+sticks[i],i);//搜索used[i]=0;if(ok==1)return;if(sticks[i]==length-now)return;//有一根木棍长度正好等于当前差值}}public static int used_reset(int used,int num){for(int i=0;i num;i++){used[i]=0;}return used;}public static int i=0;Scanner void main(String args){//Stick stick=new Stick(); scanner=new Scanner(System.in); while(true){num=Integer.parseInt(scanner.nextLine()); if(num==0)return;String s=scanner.nextLine().split("");int sum=0;for(i=0;i num;i++){//初始化sticks[i]=Integer.parseInt(s[i]);sum+=sticks[i];}Stick.sticks=Stick.sort(sticks,num); Stick.used_reset(used,num);ok=0;for(i=sticks[0];i=sum;i++){if(sum%i==0&&ok==0){Stick.ns=sum/i; used=Stick.used_reset(used,num);Stick.length=i;s(1);}}}}}