找回密码
 欢迎注册
楼主: mathe

[讨论] 毒酒问题(加强版)

  [复制链接]
发表于 2018-2-18 17:06:38 | 显示全部楼层
mathe 发表于 2018-2-18 14:46
在人数比较少时,两瓶毒酒问题的搜索算法竟然可以和果树问题非常类似。
双方问题最关键的都是搜索过程会出 ...

弱弱地问一个与本题关系不大的问题:
1人能识别出包含一瓶毒酒的2瓶酒,
2人能识别出包含一瓶毒酒的4瓶酒,
3人能识别出包含一瓶毒酒的8瓶酒,
4人能识别出包含一瓶毒酒的16瓶酒,
5人能识别出包含一瓶毒酒的32瓶酒,
6人能识别出包含一瓶毒酒的64瓶酒,
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-2-20 16:31:12 | 显示全部楼层
9个人最多只能识别17瓶正好包好两瓶毒酒的方案,而且本质上只有一种方案:
G HI EF AB DEI CFI ADH BCH ACE BDF CDG AFHI BEHI CEGH DFGH AEGI BFGI
但是9个人最多只能识别15瓶包含两瓶或一瓶毒酒的方案,可以有29种不同的识别方案
BEF DFG AEH ACG BCH GHI DEI CFI ABI ADEF ABFG BDGH EFHI CEGI CDHI
EGH DGI FHI ADF BDE CEF BFG AEI CDH ADGH BEHI CFGI ABFI BCDG ACEH
EHI FGH DGI ADE BEF CDF ABH ACI BCG AEFI BDFH CDEG ADGH BEGI CFHI
GHI DEI BFG CFH CDG BEH ADF AEG BCI EFGI BDFH CDEH AFGH ABDI ACEI
AH BG EF CI DI GHI EGH CFG DFH AFI BFI ADG BCH ACE BDE
AH BG EG DH CI FI GHI CDG CEH AEI BDI AFG BFH ABC DEF
CG BH EF AI DI FGI AGH DFH EGH CHI BDG ABF ACF BEI CDE
CH DG EF AI BI BGH AFG AEH ACD BCF BDE CGI DHI EGI FHI
CI DE FGH BGI AFI ADG BDH BCF AEH DFHI EFGI CDFG CEGH ABCH ABEI
EH ABD DFG CDI BGI CEF AEI ACH FHI ABCF BEFG DEGI AFGH BDHI CGHI
EH ADF CFG BFI ACI BEG DEI BDH GHI ABGI ACEF DEFG CDGH AFHI BCHI
EH DI AGI BFH CFG AEF BDG ACH BCI FGHI DEFG CDFH CEGI ABDH ABEI
EH FG BC DI AI BFH CEG DEF BDG CDH GHI BEI CFI AEG AFH
EI FH DG AH BI CG EGH FGI DHI ABG ACI BCH ADE BDF CEF
FG AH CH DI BE DGH AGI CFI BHI EFH EGI ADF ABF BCG CDE
FI GH CD AE BE CGI DFH AFG BHI EFH EGI ACH ADI BCF BDG
GH AC BD EI FI CFG AEH BFH DEG BCE ADF AGI BGI CHI DHI
GH BE CF DI AI BFH CEG DEF BDG CDH FGI EHI BCI AEG AFH
GH BE CF DI AI BFH CEG DFG DEH BCD EFI BGI CHI AEG AFH
GH EFG DFH ADG AEH CDI BEI ABDF ACFG BCEF DEHI BDGI CEGI AFHI BCHI
GH FI CF AD BE EFG DFH DGI EHI AHI BGI ACG BCH ABF CDE
HI AB EGH DGI ADH BEI AEF BDF CDE AFGI BFGH CDFH CEFI ACGH BCGI
HI ACEH ABDI BDEH CDEI BCFH ACFI BEFI ADFH BCGI ABGH CDGH AEGI EFGH DFGI
HI AG BF CH DE AFI BGI DGI EFI CFG DFH EGH ABH ACD BCE
HI CF BG AF DE FGI EFH DGH AGH BDF CEG BCH CDI ABI AEI
HI CG DF AB BE CFI DGH AFG BGH BFI EFH EGI ACH ADI CDE
HI CG DF EI AB FGI CFH DGH AGH BFH AEF BEG ACI BDI CDE
HI DE CFG AEI BDH ADG BEF ACH BCI EFGH DFGI ABFH ABGI CDFH CEGI
HI DG AF CF BE FGH CGI DFI BFI EGH ADH ABG BCH AEI CDE
tannis_jin曾经在百度数学吧猜测两瓶毒酒的最优方案是否总可以有某瓶酒没人喝的方案,9人17瓶酒的结论明确给出了反例。
本搜索对应的程序还比较简陋,首先里面使用bliss库对图进行标准化,但是发现bliss库有内存泄漏,于是再对大量图反复进行标准化时会导致最后内存不够用,
于是只好另外开了一个进程专门做标准化工作,而每工作一段时间重启这个进程。
但是程序运算过程还会产生大量重复数据,为了实现方便,直接调用外部命令sort对数据进行排序,结果对其中产生一个最大达到20g左右的文件进行排序就要花数小时,所以最终花费一天多才处理完9个人的情况。

点评

验证过没有问题  发表于 2018-2-25 16:13
小心的问一句:66楼的数字串是不行的吧?  发表于 2018-2-25 13:46
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-20 20:32:58 | 显示全部楼层
本帖最后由 王守恩 于 2018-2-21 08:11 编辑
mathe 发表于 2018-2-20 16:31
9个人最多只能识别17瓶正好包好两瓶毒酒的方案,而且本质上只有一种方案:
G HI EF AB DEI CFI ADH BCH AC ...



一,对于囚犯数目n,可以识别2^n坛酒(其中有1坛毒酒)
1,n=1,可以识别2坛酒(其中有1坛毒酒)
       n1=1
2,n=2,可以识别4坛酒(其中有1坛毒酒)
       n1=1+2
       n2=1+3
3,n=3,可以识别8坛酒(其中有1坛毒酒)
       n1=1+2+3+4
       n2=1+2+5+6
       n3=1+3+5+7
4,n=4,可以识别16坛酒(其中有1坛毒酒)
       n1=1+2+3+4+5+ 6 + 7 + 8
       n2=1+2+5+6+9+10+11+12
       n3=1+3+5+6+9+10+13+14
       n4=1+3+5+7+9+11+13+15
5,n=5,可以识别32坛酒(其中有1坛毒酒)
       n1=1+2+3+4+5+ 6 + 7 + 8 + 9 +10+11+12+13+14+15+16
       n2=1+2+3+4+5+ 6 + 7 + 8 +17+18+19+20+21+22+23+24
       n3=1+2+3+4+9+10+11+12+17+18+19+20+25+26+27+28
       n4=1+2+5+6+9+10+13+14+17+18+21+22+25+26+29+30
       n5=1+3+5+7+9+11+13+15+17+19+21+23+25+27+29+31
.............

二,对于囚犯数目n,可以识别n+1坛酒(其中有2坛毒酒)
1,n=2,可以识别3坛酒(其中有2坛毒酒)
       n1=1
       n2=2

2,n=3,可以识别4坛酒(其中有2坛毒酒)
       n1=1
       n2=2
       n3=3

3,n=4,可以识别5坛酒(其中有2坛毒酒)
       n1=1
       n2=2
       n3=3
       n4=4
   
4,n=5,可以识别6坛酒(其中有2坛毒酒)
       n1=1
       n2=2
       n3=3
       n4=4
       n5=5
   
5,n=6,可以识别8坛酒(其中有2坛毒酒)
       n1=1+2+3
       n2=1+4+5
       n3=2+4+6
       n4=3+5+6
       n5=3+4+7      
       n6=2+5+7

6,n=7,可以识别10坛酒(其中有2坛毒酒)
       n1=1+2+3
       n2=1+4+5
       n3=2+4+6
       n4=3+4+7
       n5=2+5+8      
       n6=1+6+9
       n7=7+8+9
   
7,对于n=8,至少可以识别13坛酒(其中有2坛毒酒):
       n1=1+2+ 3 + 4
       n2=1+5+ 6 + 7
       n3=2+5+ 8 + 9
       n4=3+6+ 8 +10
       n5=4+7+ 8 +11      
       n6=1+9+10+11
       n7=4+6+ 9 +12
       n8=2+7+10+12
   
8,对于n=9,至少可以识别16坛酒(其中有2坛毒酒):
       n1=1+ 2 + 3 + 4
       n2=5+ 6 + 7
       n3=1+ 5 + 8 +11+12
       n4=2+11+13+14
       n5=3+ 6 + 8 + 9 +13      
       n6=4+ 6 +10+12+13
       n7=1+ 5 + 9 +10+14
       n8=4+ 9 +11+15
       n9=2+ 7 + 8 +10+15
        
9,n=10,至少20坛酒(其中有2坛毒酒)
       n 1 =1+2+ 3 + 4 + 5 + 6
       n 2 =1+2+ 7 + 8 + 9
       n 3 =3+4+ 7 +11
       n 4 =3+5+10+12+15+16
       n 5 =1+6+15+17+18      
       n 6 =5+6+ 8 +11+12+13+17
       n 7 =2+4+ 9 +11+14+16+17
       n 8 =2+5+10+13+14+18
       n 9 =1+4+ 9 +13+15+19
       n10=3+6+ 7 +12+14+19
.............
mathe!能把122楼翻译成上面的格式吗?
      
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-24 19:06:45 | 显示全部楼层
本帖最后由 王守恩 于 2018-2-24 19:08 编辑
mathe 发表于 2018-2-20 16:31
9个人最多只能识别17瓶正好包好两瓶毒酒的方案,而且本质上只有一种方案:
G HI EF AB DEI CFI ADH BCH AC ...

n个人,最多只能识别m瓶正好包含两瓶毒酒的方案,等同下面的题目:
n个连续正整数(从“1”开始),最多只能组成(m - 1)个组合数。组合数算法规定2条:
1,每个组合数取n个连续正整数中的若干个(1个——n个)作加数,用“+”连接而成;
2,比较任意2个组合数,不允许有1个组合数的加数包含了另1个组合数的所有加数。
譬如:
n=2,m  - 1=2    组合数=1,2
n=3,m  - 1=3    组合数=1,2,3
n=4,m  - 1=4    组合数=1,2,3,4
n=5,m  - 1=5    组合数=1+2,1+5,2+3,3+4,4+5
n=6,m  - 1=7    组合数=1+5,2+3,4+6,1+2+6,1+3+4,2+4+5,3=5+6
n=7,m  - 1=9    组合数=1+2,1+3,1+4,2+5,3+6,4+7,2+6+7,3+5+7,4+5+6
n=8,m  - 1=12    组合数=1+2,3+4,5+8,6+7,1+3+5,1+4+7,1+6+8,2+3+6,2+4+8,2+5+7,3+7+8,4+5+6
n=9,m  - 1=16    组合数=1+2,1+8,3+6,4+7,5+9,1+3+4,1+5+7,1+8+9,2+3+5,2+4+9,2+6+7,3+7+8,3+7+9,4+5+6,4+5+8
n=10,m  - 1=19    组合数=1+2,4+7,5+9,1+3+4,1+5+7,1+8+9,2+3+5,2+4+9,2+6+7,3+4+6,3+7+8,4+5+6,4+5+8,1+5+6+10,
                                          1+7+8+10,2+4+8+10,2+6+9+10,3+4+9+10,3+5+7+10
...........


补充内容 (2018-2-25 10:28):
n个连续正整数(从“1”开始)=喝酒的人数,最多只能组成(m - 1)个组合数=酒的瓶数。每个组合数代码=每瓶酒对应喝酒人的编号。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-26 15:25:12 | 显示全部楼层
mathe 发表于 2018-2-20 16:31
9个人最多只能识别17瓶正好包好两瓶毒酒的方案,而且本质上只有一种方案:
G HI EF AB DEI CFI ADH BCH AC ...

谢谢mathe!此题让我长进不少!
总算把题目的来龙去脉搞清楚了!
124楼的解法还是没有问题!我还是想再往前推一推!
谢谢mathe!能否把66楼的资料多给一些!

点评

谢谢mathe!  发表于 2018-3-1 11:20
66#有链接,内容就是从那里复制的,我也没有更多信息,不知道他是怎么找到的。  发表于 2018-3-1 10:32
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-28 12:37:37 | 显示全部楼层
本帖最后由 王守恩 于 2018-2-28 18:52 编辑
王守恩 发表于 2018-2-26 15:25
谢谢mathe!此题让我长进不少!
总算把题目的来龙去脉搞清楚了!
124楼的解法还是没有问题!我还是想再 ...

我来把题目改一下,题意不变:
每个开关有2个功能:开或者关。每盏灯只有2种状况:亮或者不亮。
问:用n个开关,最多能控制m盏灯,恰好让其中的任意2盏灯亮起来?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-3-1 10:42:50 | 显示全部楼层
9个人的问题,我开始使用BLISS库来过滤重复的搜索,但是后来发现BLISS库有严重的内存泄漏问题
后来改成使用nauty库: http://pallini.di.uniroma1.it/
这个库编译以后可以有多个不同版本,比如 nauty.a nautyL.a nautyL1.a nautyW.a 等
对于人数比较少时,如果人的数目加酒的数目不超过64,可以使用nautyL1.a会有比较好的效率
下面代码可以完成这个穷举工作,其中K=8(8个人)的代码很快可以运行完,但是9个人就需要运行1天多了
而10个人估计就要很长时间了。
代码会输出一些中间结果,如果将那些中间结果作为输入,代码可以自动从这些中间结果处继续开始
  1. #include <set>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5. #include <stdio.h>
  6. #include <string.h>
  7. #include <stdlib.h>
  8. #define MAXN 64
  9. #include "nauty/nauty.h"

  10. typedef unsigned int dtype;
  11. typedef std::set<dtype> UnionState;
  12. typedef std::vector<dtype> DataState;
  13. int bestn;
  14. #define UB   65
  15. #ifndef K
  16. #define K    9
  17. #endif
  18. #if K==8
  19. #define HK 3
  20. #define DUMP_RANGE 12
  21. #endif
  22. #if K == 9
  23. #define HK   4
  24. #define DUMP_RANGE 16
  25. #endif
  26. #if K == 10
  27. #define HK  5
  28. #define DUMP_RANGE 20
  29. #endif

  30. typedef struct _TGRAPH{
  31.     graph data[MAXN];
  32.     bool operator<(const struct _TGRAPH& g)const{
  33.          int i;
  34.          for(i=0;i<MAXN;i++){
  35.             if(data[i]<g.data[i])return true;
  36.             if(data[i]>g.data[i])return false;
  37.          }
  38.          return false;
  39.     }
  40.     bool operator==(const struct _TGRAPH& g)const{
  41.          int i;
  42.          for(i=0;i<MAXN;i++){
  43.             if(data[i]!=g.data[i])return false;
  44.          }
  45.          return true;
  46.     }
  47.     _TGRAPH(){memset(data,0,sizeof(data));}
  48.     _TGRAPH(const graph g[MAXN]){memcpy(data,g,sizeof(data));}
  49. }TGRAPH;

  50. int compg(const void *p, const void *q)
  51. {
  52.     const TGRAPH *g1=(const TGRAPH *)p;
  53.     const TGRAPH *g2=(const TGRAPH *)q;
  54.     int i;
  55.     for(i=0;i<MAXN;i++){
  56.        if(g1->data[i]<g2->data[i])return -1;
  57.        if(g1->data[i]>g2->data[i])return 1;
  58.     }
  59.     return 0;
  60. }

  61. UnionState us[UB];
  62. DataState ds;
  63. int curlevel;
  64. int curbest;
  65. #define tus us[curlevel]
  66. graph allg[UB][MAXN];
  67. graph normg[UB][MAXN];
  68. std::set<TGRAPH> usedg[UB];

  69. void graph_remove_node(graph g[MAXN], graph ng[MAXN], int node, int n)
  70. {
  71.     int i;
  72.     graph lm,rm;
  73.     if(node>0){
  74.         memcpy(ng, g, sizeof(g[0])*node);
  75.     }
  76.     if(node<n-1){
  77.         memcpy(&ng[node],&g[node+1], sizeof(g[0])*(n-1-node));
  78.     }
  79.     memset(&ng[n-1], 0, sizeof(g[0])*(MAXN-n+1));
  80.     if(node == 0){
  81.        for(i=0;i<n-1;i++){
  82.           ng[i]<<=1;
  83.        }
  84.     }else{
  85.        lm=(1ULL<<node)-1;
  86.        lm<<=64-node;
  87.        rm=(1ULL<<(63-node))-1;
  88.        for(i=0;i<n-1;i++){
  89.           graph h=ng[i];
  90.           ng[i] = (h&lm)|((h&rm)<<1);
  91.        }
  92.     }
  93. }

  94. void dump_normalized(graph g[MAXN],graph ng[MAXN], int orbits[MAXN], int n)
  95. {
  96.     int i,j,e;
  97.     int lab[MAXN], ptn[MAXN];
  98.     static DEFAULTOPTIONS_GRAPH(options);
  99.     statsblk stats;
  100.     int m,v;
  101.     memset(ng,0,sizeof(ng[0])*MAXN);

  102.     m=SETWORDSNEEDED(n);
  103.     nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
  104.     options.getcanon = TRUE;
  105.     options.defaultptn = FALSE;
  106.     for(i=0;i<n;++i){
  107.       lab[i]=i;
  108.     }
  109.     for(i=0;i<n;++i){
  110.       ptn[i]=1;
  111.     }
  112.     ptn[K-1]=0;
  113.     ptn[n-1]=0;
  114.     densenauty(g, lab, ptn, orbits, &options, &stats, m, n, ng);
  115. }

  116. void init()
  117. {
  118.     curlevel = 0;
  119.     ds.clear();
  120.     us[0].clear();
  121. }
  122. int bitcount(dtype d);
  123. int test_add(dtype d)
  124. {
  125.     UnionState ls;
  126.     if(bitcount(d)>HK)return -1;
  127. #ifdef STRICT
  128.     if(tus.find(d)!=tus.end()){
  129.          return -1;
  130.     }
  131.     ls.insert(d);
  132. #endif
  133.     int i;
  134.     for(i=0;i<ds.size();++i){
  135.         if(ds[i]==d)return -1;
  136.         dtype u=d|ds[i];
  137.         if(tus.find(u)!=tus.end()){
  138.             return -1;
  139.         }
  140.         if(ls.find(u)!=ls.end()){
  141.            return -1;
  142.         }
  143.         ls.insert(u);
  144.     }
  145.     return 0;
  146. }

  147. int bitcount(dtype d){
  148.     int i,b=0;
  149.     for(i=0;i<K;i++){
  150.        if(d&(1<<i))b++;
  151.     }
  152.     return b;
  153. }

  154. void do_add(dtype d){
  155.     int i;
  156. #ifdef STRICT
  157.     tus.insert(d);
  158. #endif
  159.     for(i=0;i<ds.size();++i){
  160.         dtype u=d|ds[i];
  161.         tus.insert(u);
  162.     }
  163.     ds.push_back(d);
  164. }

  165. void pop()
  166. {
  167.    ds.pop_back();
  168.    curlevel--;
  169. }


  170. void dumpg(int n, int is_best)
  171. {
  172.     int i;
  173.     if(is_best){
  174.        printf("Best edge %d\n\t",n-K);
  175.     }else{
  176.        printf("More edge %d\n\t",n-K);
  177.     }
  178.     for(i=K;i<n;i++){
  179.        printf("%llx ",allg[curlevel][i]>>(64-K));
  180.     }
  181.     printf("\n");
  182.     fflush(stdout);
  183. }

  184. FILE *fout;
  185. void search(int n, dtype initvalue[UB], int nextstep, int& maxstep)
  186. {
  187.     int i,j;
  188.     int orbits[MAXN],orbits2[MAXN];
  189.     usedg[curlevel].clear();
  190.     graph g[MAXN], ng[MAXN];
  191.     memset(g,0,sizeof(g));
  192.     memset(ng,0,sizeof(ng));
  193.     if(bestn<n-1){
  194.         bestn=n-1;
  195.         dumpg(bestn,1);
  196.     }else if(n-1>=DUMP_RANGE+K){
  197.         dumpg(n-1, 0);
  198.     }
  199.     for(i=1;i<1<<K;++i){
  200.        if(test_add(i)==0){
  201.            memcpy(allg[curlevel+1],allg[curlevel],sizeof(allg[0]));
  202.            for(j=0;j<K;j++){
  203.               if(i&(1<<j)){
  204.                  ADDONEEDGE(allg[curlevel+1],K-1-j,n-1,1);
  205.               }
  206.            }
  207.            dump_normalized(allg[curlevel+1],normg[curlevel+1],orbits,n);
  208.            TGRAPH t(normg[curlevel+1]);
  209.            if(usedg[curlevel].find(t)!=usedg[curlevel].end()){
  210.                continue;
  211.            }
  212.            for(j=K;j<n-1;j++){
  213.               if(orbits[j]==j && orbits[n-1]!=j){
  214.                   graph_remove_node(allg[curlevel+1], g, j, n);
  215.                   dump_normalized(g, ng, orbits2, n-1);
  216.                   int c=compg(ng, normg[curlevel]);
  217.                   if(c<0)break;
  218.               }
  219.            }
  220.            if(j<n-1)continue;
  221.            usedg[curlevel].insert(t);
  222.            if(maxstep>0){
  223.                if(allg[curlevel+1][K+nextstep]>>(64-K) != initvalue[nextstep]){
  224.                   continue;
  225.                }
  226.            }
  227.            us[curlevel+1]=us[curlevel];
  228.            curlevel++;
  229.            do_add(i);
  230.            if(nextstep+1==maxstep)maxstep=0;
  231.            search(n+1, initvalue, nextstep+1, maxstep);
  232.            pop();
  233.        }
  234.     }
  235. }

  236. int main(int argc, const char *argv[])
  237. {
  238.     int i,j,n;
  239.     int cc=argc-1;
  240.     dtype initvalue[UB];
  241.     for(i=1;i<argc;i++){
  242.          char *endp=NULL;
  243.          initvalue[i-1]=strtol(argv[i],&endp, 16);
  244.     }
  245.     int orbits[MAXN];
  246.     if(cc>=1){
  247.         dtype r=0;
  248.         for(j=K-1;j>=0;j--){
  249.            if((initvalue[0]&(1<<j))==0)break;
  250.            r|=1<<j;
  251.         }
  252.         if(r!=initvalue[0]||r==0){
  253.            fprintf(stderr,"Invalid start value\n");
  254.            return -1;
  255.         }
  256.         if(cc==1)cc=0;
  257.     }else{
  258.         j=K-2;
  259.         cc=0;
  260.     }
  261.     for(i=K-1-j;i<=HK;i++){
  262.         fprintf(stderr, "searh for i=%d\n",i);
  263.         dtype d=0;
  264.         n=K+1;
  265.         EMPTYGRAPH(allg[0],1,n);
  266.         for(j=0;j<i;j++){
  267.             ADDONEEDGE(allg[0], j, K, 1);
  268.         }
  269.         init();
  270.         dump_normalized(allg[0], normg[0], orbits, n);
  271.         d=allg[0][K]>>(64-K);
  272.         do_add(d);
  273.         search(n+1, initvalue, 1, cc);
  274.     }
  275.     return 0;
  276. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-3-5 18:36:08 | 显示全部楼层
mathe 发表于 2018-3-1 10:42
9个人的问题,我开始使用BLISS库来过滤重复的搜索,但是后来发现BLISS库有严重的内存泄漏问题
后来改成使 ...

一年来粘着”‘数学研发论坛’“这座宝库!收获真是不少!
66#的方法应该是最好的,可惜只给到12,若能给到15(再来3个),.....
请网友搜索给个链接,感谢不尽!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-3-14 10:35:11 | 显示全部楼层
mathe 发表于 2018-3-1 10:42
9个人的问题,我开始使用BLISS库来过滤重复的搜索,但是后来发现BLISS库有严重的内存泄漏问题
后来改成使 ...

66#的方法应该是最好的,可惜只给到12,若能再来3个(1个也好),是不是我们的信息太封闭了?

点评

66#已经有链接了,能搜索到的信息就这么多。 而127#的代码对于10个人估计至少要计算上千年,所以不可行。 我试着随机搜索了一下,可以找出上千个10人21瓶毒酒的结果,但是没有找到22的情况  发表于 2018-3-15 18:49
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-3-17 08:10:40 | 显示全部楼层
mathe 发表于 2018-3-1 10:42
9个人的问题,我开始使用BLISS库来过滤重复的搜索,但是后来发现BLISS库有严重的内存泄漏问题
后来改成使 ...

敬佩楼主对此题倾注了不少的心力。
我们不妨先来约定几条,问题也许会简单些:
1,从左到右:”1“出现少的排前面。
2,从上到下:”1“出现少的排前面
3,从上到下:”1“出现相同时,按从小到大排列。
     譬如:a(10) >= 22(修改).
1,从左到右:按”1“出现6,7,8的排列。
2,从上到下:按”1“出现1,2,3,4的排列
3,从上到下:”1“出现相同时,按从小到大排列。
原则是:如果把22瓶酒换成十进制数,总和尽可能小。
a(10) >= 22.
   1,1010110000
   2,1110000000
   3,0010011000
   4,0110100001
   5,1000010101
   6,0011000101
   7,1001000000
   8,0000000010
   9,0001110100
10,0001001000
11,0010101010
12,1100010010
13,0000010001
14,0000101101
15,0100010100
16,0000011110
17,0100101000
18,0001100011
19,0000100100
20,0101000001
21,0101000110
22,1010000011
a(10) >= 22(修改).
   8,0000010000
13,0000000011
10,0000100100
19,0001001000
   7,0100000100
20,0010000101
15,0010001010
17,0011100000
   3,1000100010
   2,1110000000
16,0000111010
   9,0001001110
18,0001010101
14,0001101001
21,0010011100
   5,0100001011
   1,0100100110
12,0110010010
   6,1000001101
11,1001110000
   4,1011000001
22,1100010001
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-12-23 04:23 , Processed in 0.035129 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表