Chinaunix

标题: euler project第18题求解 [打印本页]
作者: sequencing    时间: 2012-06-11 09:49
标题: euler project第18题求解
欧拉计划第18题(http://projecteuler.net/problem=18)
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

    3
  7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

                            75
                          95  64
                        17  47  82
                      18  35  87  10
                    20  04  82  47  65
                  19  01  23  75  03  34
                88  02  77  73  07  63  67
              99  65  04  28  06  16  70  92
            41  41  26  56  83  40  80  70  33
          41  48  72  33  47  32  37  16  94  29
        53  71  44  65  25  43  91  52  97  51  14
      70  11  33  28  77  73  17  78  39  68  17  57
    91  71  52  38  17  14  91  43  58  50  27  29  48
  63  66  04  68  89  53  67  30  73  16  69  87  40  31
04  62  98  27  23  09  70  98  73  93  38  53  60  04  23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)
请教大家这类问题暴力破解怎么入手，谢谢各位！
作者: yinyuemi    时间: 2012-06-11 10:35
本帖最后由 yinyuemi 于 2012-06-11 10:36 编辑

回复 1# sequencing


    决策树（递归）？
作者: sequencing    时间: 2012-06-11 10:43
yinyuemi 发表于 2012-06-11 10:35
回复 1# sequencing
搜索时发现多说用动态规划
作者: Honey-pot    时间: 2012-06-11 11:59
提示: 作者被禁止或删除 内容自动屏蔽
作者: Honey-pot    时间: 2012-06-11 13:47
提示: 作者被禁止或删除 内容自动屏蔽
作者: sequencing    时间: 2012-06-11 14:16
Honey-pot 发表于 2012-06-11 13:47
局部最优不一定全局最优
作者: Honey-pot    时间: 2012-06-11 14:45
提示: 作者被禁止或删除 内容自动屏蔽
作者: Honey-pot    时间: 2012-06-11 15:22
提示: 作者被禁止或删除 内容自动屏蔽
作者: sequencing    时间: 2012-06-11 15:50
Honey-pot 发表于 2012-06-11 15:22
明白了，多谢！
要是挨个尝试的话，怎么写将所有情况都考虑进去呢
作者: Honey-pot    时间: 2012-06-11 15:57
提示: 作者被禁止或删除 内容自动屏蔽
作者: yinyuemi    时间: 2012-06-12 03:57
回复 9# sequencing


    暴力解法（gawk 4.0.0）：
  1. gawk '{for(i=1;i<=NF;i++)a[NR][i]=$i}
  2. END{f(a[1][1],a[1][1],1,1);print max,cob}
  3. function f(sum,com,x,y){
  4. if(x==NR){print sum,com;if(max<sum){max=sum;cob=com};return -1}
  5. else{if(a[x+1][y]>=a[x+1][y+1]){
  6.   f(sum+a[x+1][y],com FS a[x+1][1],x+1,y)
  7.   f(sum+a[x+1][y+1],com FS a[x+1][1],x+1,y+1)}
  8. else{
  9.   f(sum+a[x+1][y+1],com FS a[x+1][1],x+1,y+1)
  10.   f(sum+a[x+1][y],com FS a[x+1][1],x+1,y)}
  11. }
  12. }'
复制代码
作者: jils2013    时间: 2012-06-12 10:28
本帖最后由 jils2013 于 2012-06-12 10:55 编辑

逻辑：路由数量等于2^n个；对每个数字做2进制转化，然后藉此作左右摆动控制路由

简单修改了逻辑，打印出路由经过的数字。
  1. [root@localhost shell]# cat -vte file1
  2.                             75$
  3.                           95  64$
  4.                         17  47  82$
  5.                       18  35  87  10$
  6.                     20  04  82  47  65$
  7.                   19  01  23  75  03  34$
  8.                 88  02  77  73  07  63  67$
  9.               99  65  04  28  06  16  70  92$
  10.             41  41  26  56  83  40  80  70  33$
  11.           41  48  72  33  47  32  37  16  94  29$
  12.         53  71  44  65  25  43  91  52  97  51  14$
  13.       70  11  33  28  77  73  17  78  39  68  17  57$
  14.     91  71  52  38  17  14  91  43  58  50  27  29  48$
  15.   63  66  04  68  89  53  67  30  73  16  69  87  40  31$
  16. 04  62  98  27  23  09  70  98  73  93  38  53  60  04  23$
  17. [root@localhost shell]# awk 'function binary(num){str="";while(num!=0){str=num%2str;num=int(num/2);};return sprintf("%0"bn"d",str)}
  18.          {bn=NR;for(i=1;i<=NF;i++)ar[NR,i]=$i;}
  19.          END{for(i=0;i<2^bn;i++)
  20.                   {split(binary(i),bit,"");list="";
  21.                    for(n=1;n<=bn;n++){if(n==1){r=1}else{r+=bit[n]};sum[i]+=ar[n,r];list=list" "ar[n,r]};
  22.                    if(sum[i]>max){max=sum[i];maxlist=list}
  23.                   }
  24.                    print max,maxlist;
  25.                }' file1
  26. 1074  75 64 82 87 82 75 73 28 83 32 91 78 58 73 93   
复制代码
作者: jils2013    时间: 2012-06-12 10:40
yinyuemi 发表于 2012-06-12 03:57
回复 9# sequencing


能说下具体逻辑吗？我看了会，晕了
作者: yinyuemi    时间: 2012-06-12 13:01
回复 13# jils2013


    用递归遍历全部可能路径，每次走完一次，计算总和，并和当前的最大值比较，之后保存路径和总和
作者: jason680    时间: 2012-06-12 18:35
本帖最后由 jason680 于 2012-06-12 19:39 编辑

回复 1# sequencing

how about this
$ awk '{for(n=0;n++<NF;)s[NR,n]=a[NR,n]=$n}END{c[0,0]=1;for(n=NR;n>1;n--)for(t=0;++t<n;)if(s[n,t]>s[n,t+1]){c[n-1,t]=t;s[n-1,t]+=s[n,t]}else{c[n-1,t]=t+1;s[n-1,t]+=s[n,t+1]};m=0;for(n=0;n++<NR;){for(p=NR-n;p-->0;)printf "  ";for(t=0;t++<n;){if(c[n-1,m]==t)a[n,t]="\033[31m"a[n,t]"\033[0m";printf a[n,t]"  "};m=c[n-1,m];print ""}print "max="s[1,1]}' ep18




# for min   
$ awk '{for(n=0;n++<NF;)s[NR,n]=a[NR,n]=$n}END{c[0,0]=1;for(n=NR;n>1;n--)for(t=0;++t<n;)if(s[n,t]<s[n,t+1]){c[n-1,t]=t;s[n-1,t]+=s[n,t]}else{c[n-1,t]=t+1;s[n-1,t]+=s[n,t+1]};m=0;for(n=0;n++<NR;){for(p=NR-n;p-->0;)printf "  ";for(t=0;t++<n;){if(c[n-1,m]==t)a[n,t]="\033[31m"a[n,t]"\033[0m";printf a[n,t]"  "};m=c[n-1,m];print ""}print "min="s[1,1]}' ep18
作者: Honey-pot    时间: 2012-06-12 20:32
提示: 作者被禁止或删除 内容自动屏蔽
作者: Honey-pot    时间: 2012-06-12 21:13
提示: 作者被禁止或删除 内容自动屏蔽



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2