两颗砝码称连续整数重量

Sat, 2nd November 2019Edit on Githubcombination algorithm

摘要

王守恩于2017年1月提出一个使用天平称重问题。问题是如何选择20种不同整数重量的砝码（每种重量的砝码可以有多颗），在每次称重时在天平一边（不能是两边）放两颗（不能是一颗，也不能是三颗或以上）上述整数重量砝码，使得可以称出的连续整数重量尽量多？
这个问题其实就是要求找出n个整数，使得其中两个整数（可以重复选择同样的整数两次）之和能够覆盖的连续整数区间最大化。
lsr314很快指出可以称出100个连续整数重量,而一个很宽松的理论上界是210个。
最终我们得到了141个连续整数重量的方案，并且使用构造方法计算出使用86种不同整数砝码可以得出2257个连续整数重量的方案。
所有得到结果如下图，其中横坐标为砝码不同重量数目，纵坐标为最大连续数目减1除以2.
balance_stat

详细内容

在王守恩提出这个问题后，lsr314宣称可以称出100个连续整数重量并且发现这是Rohrbach's problem 王守恩随后构造出了104种连续重量方案

我们用1,2,3,4,5,6,7,14,21,28,35,42,49,56,63,70,77,84,91,98这20套砝码：
2=1+1   3=1+2     4=1+3     5=1+4   6=1+5       7=1+6
8=7+1   9=7+2   10=7+3   11=7+4   12=7+5   13=7+6   14=7+7
15=14+1
16=14+2
17=14+3
18=14+4
19=14+5
20=14+6
21=14+7
............
98=91+7
99=98+1
100=98+2
101=98+3
102=98+4
103=98+5
104=98+6
105=98+7
这20套砝码可以称出2——105共104种连续整数重量。

在2017年7月1日，northwolves分别给出了116，119，120个连续整数的方案

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 26, 39, 52, 65, 78, 91, 104  116个
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 24, 36, 48, 60, 72, 84, 96, 108  119个
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 22, 33, 44, 55, 66, 77, 88, 99, 110  120个

然后他把问题发布在了excelhome网站, 论坛里的川香群子踊跃参与并且给出了VB代码
借用这个代码northwolves找出了更多120个连续整数的方案。川香群子更是把结果更新到129个连续整数

120_2-121        1,2,3,4,5,6,7,8,9,10,11,22,32,44,52,64,76,88,98,110
121_2-122        1,2,3,4,5,6,7,9,10,19,22,23,33,44,55,66,77,88,99,110
127_2-128        1,2,3,4,5,6,7,9,10,20,23,24,32,44,56,68,80,92,104,116
128_2-129        1,2,3,4,5,6,7,10,12,20,21,23,33,45,57,69,81,93,105,117
129_2-130        1,2,3,4,5,6,8,11,12,19,21,22,34,46,58,70,82,94,106,118

在重新对代码进行优化剪纸后她把结果更新到134个

134,1,2,3,6,8,11,12,20,22,23,26,30,31,44,57,70,83,96,109,122
134,1,2,4,5,8,9,10,17,18,22,25,36,47,58,69,80,91,102,113,124

下面是川香群子的最终代码

Dim a&(), b(), k&, k1&, k2&, n&, t2&, tms#
Sub Num_Check() 'by kagawa 2017/7/5
    tms = Timer
    
    n = 20 '组合个数n
    
    ReDim a(1 To n), b(1 To n), c&(1 To 2000) '理论最大数允许1000 实际最大数124
    '数组a记录组合、数组b记录各位数组合的检查状态结果、数组c记录本组合的具体检查状态
    
    a(1) = 1: c(1) = 2: c(2) = 1: b(1) = c '数组初始化赋值
    
    k = 0: k1 = 0: k2 = 0 '递归次数k、完成组合次数k1、有效组合个数k2 初始化归零
    t2 = 121 '设置记录起始目标值
    
    Call dgZH(1, 2) '调用递归过程进行1-m中任选n个数的组合
    
    MsgBox Format(Timer - tms, "0.00s") & k & "/" & k1 & "/" & k2
End Sub
Sub dgZH(i&, t&) '从1-m中选n个数的递归组合过程
    Dim j&, t1&
    k = k + 1 '递归次数
    If k Mod 10000 = 0 Then
        DoEvents
        Application.StatusBar = Format(Timer - tms, "0.0s ") & t2 & "/" & k & "/" & k1 & "/" & k2
    End If
    
    For j = i + 1 To i + 13 '限制取数范围 为前数+13
        a(t) = j '记录该取数j
        t1 = Chk(t) '计算统计到t个数时的最大连续个数
        
'        If t > 16 Then If t1 < (t - 16) * 10 + 65 Then Exit For
        If t > 11 Then If t1 < (t - 11) * 10 + 15 Then Exit For '最新的剪枝更严格
        '连续数未达到一定值时判断为低效组合 剪枝舍去后面不用再算
        
        If t1 < j - 1 Then Exit For
        '连续数缺口比当前值小时 表明加入当前值无效因此剪枝退出 (实为t1+2<j+1 的简化)
        
        If t < n Then '组合不足n个数时继续向下递归取数
            Call dgZH(j, t + 1)
        Else '组合=n个数时
            k1 = k1 + 1 '记录完成组合的个数
            If t1 >= t2 Then
                k2 = k2 + 1: t2 = t1
                Cells(k2, 1) = Timer - tms
                Cells(k2, 2) = k: Cells(k2, 3) = k1
                Cells(k2, 4) = t2: Cells(k2, 5).Resize(, n) = a
            End If
        End If
    Next
End Sub
Function Chk&(t&) '检查到数位t时的最大连续个数
    Dim c&(), i&, t1&
    c = b(t - 1) '继承上一数位的检查结果状态 便于快速计算
    t1 = a(t) '当前加入数t1
    For i = 1 To t
        c(t1 + a(i)) = 1 '记录增加的两两相加之和
    Next
    For i = c(1) To t1 + t1 '仅需检查上一数位空缺位置之后是否能连续
        If c(i) = 0 Then Exit For '不连续时退出
    Next
    c(1) = i '记录本次空缺位置 以便今后快速计算
    b(t) = c '本数位的检查结果记录到数组b 以便后续调用
    Chk = i - 2 '返回实际最大连续个数
End Function

2018年4月，这个问题引起了mathe的注意。他觉得这个问题和两瓶毒酒问题很类似，不过很显然他这个感觉不太准，后面他使用的方法和那个问题中的方案完全不同。 mathe觉得前面已经得出的134个连续整数的结果还不够好，一个良好的结果应该满足对称性,也就是相邻数的差应该接近左右对称。并且他给出了两份C代码分别用于穷举 n是奇数和n是偶数情况的解。但是为了能够更加有效的搜索，他对数据做了额外的限制，要求最小的数字等于0（这个不影响结果），而覆盖的连续整数数目要求正好等于最大整数的两倍加1，也就是这n个数中任意两数之和都要落在这个指定的有效范围之内。
结果显示n=11时最优解不完全对称，但是这是唯一一组不完全对称的最优解。

[47] 0 1 2 3 7 11 15 19 21 22 24
[47] 0 1 2 5 7 11 15 19 21 22 24

根据已经穷举出来的最优解，mathe发现最优结果相邻数的差具有强烈的规律性

3:
[5] 0 1 2 {1 1}
4:
[9] 0 1 3 4 {1 2 1}
5:
[13] 0 1 3 5 6 {1 2 2 1}
6:
[17] 0 1 3 5 7 8 {1 2 2 2 1}
7:
[21] 0 1 2 5 8 9 10 {1 1 3 3 1 1}
[21] 0 1 3 5 7 9 10 {1 2 2 2 2 1}
8:
[27] 0 1 3 4 9 10 12 13  {1 2 1 5 1 2 1}
[27] 0 1 2 5 8 11 12 13  {1 1 3 3 3 1 1}
9:
[33] 0 1 2 5 8 11 14 15 16 {1 1 3 3 3 3 1 1}
10:
[41] 0 1 3 4 9 11 16 17 19 20 {1 2 1 5 2 5 1 2 1}
11:
[45] 0 1 3 4 6 11 13 18 19 21 22 {1 2 1 2 5 2 5 1 2 1}
[45] 0 1 2 3 7 11 15 19 2
[45] 0 1 2 3 7 11 15 19 20 21 22 {1 1 1 4 4 4 4 1 1 1}
[45] 0 1 2 3 7 11 15 17 20 21 22 {1 1 1 4 4 4 2 3 1 1}
[45] 0 1 2 5 7 11 15 17 20 21 22 {1 1 3 2 4 4 2 3 1 1}
[45] 0 1 2 5 8 11 14 17 20 21 22 {1 1 3 3 3 3 3 3 1 1}
[45] 0 1 3 4 9 11 13 18 19 21 22 {1 2 1 5 2 2 5 1 2 1}
12:
[55] 0 1 3 5 6 13 14 21 22 24 26 27 {1 2 2 1 7 1 7 1 2 2 1}
[55] 0 1 3 4 9 11 16 18 23 24 26 27 {1 2 1 5 2 5 2 5 1 2 1}
13：
[65] 0 1 3 4 9 11 16 21 23 28 29 31 32 {1 2 1 5 2 5 5 2 5 1 2 1}
14：
[73] 0 1 3 4 9 11 16 20 25 27 32 33 35 36 {1 2 1 5 2 5 4 5 2 5 1 2 1}
15：
[81] 0 1 3 4 5 8 14 20 26 32 35 36 37 39 40 {1 2 1 1 3 6 6 6 6 3 1 1 2 1}
16：
[93] 0 1 3 4 5 8 14 20 26 32 38 41 42 43 45 46 {1 2 1 1 3 6 6 6 6 6 3 1 1 2 1}
17：
[105] 0 1 3 4 5 8 14 20 26 32 38 44 47 48 49 51 52 {1 2 1 1 3 6 6 6 6 6 6 3 1 1 2 1}
18：
[117] 0 1 3 4 5 8 14 20 26 32 38 44 50 53 54 55 57 58 {1 2 1 1 3 6 6 6 6 6 6 6 3 1 1 2 1}
19：
[129] 0 1 3 4 5 8 14 20 26 32 38 44 50 56 59 60 61 63 64 {1 2 1 1 3 6 6 6 6 6 6 6 6 3 1 1 2 1}
20：
[141] 0 1 3 4 5 8 14 20 26 32 38 44 50 56 62 65 66 67 69 70 {1 2 1 1 3 6 6 6 6 6 6 6 6 6 3 1 1 2 1}
21：
[153] 0 1 3 4 5 8 14 20 26 32 38 44 50 56 62 68 71 72 73 75 76 {1 2 1 1 3 6 6 6 6 6 6 6 6 6 6 3 1 1 2 1}
22：
[165] 0 1 3 4 6 10 13 15 21 29 37 45 53 61 67 69 72 76 78 79 81 82 {1 2 1 2 4 3 2 6 8 8 8 8 8 6 2 3 4 2 1 2 1}
[165] 0 1 3 4 5 8 14 20 26 32 38 44 50 56 62 68 74 77 78 79 81 82 {1 2 1 1 3 6 6 6 6 6 6 6 6 6 6 6 3 1 1 2 1}
23：
[181] 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 75 77 80 84 86 87 89 90 {1 2 1 2 4 3 2 6 8 8 8 8 8 8 6 2 3 4 2 1 2 1}
24：
[197] 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 77 83 85 88 92 94 95 97 98 {1 2 1 2 4 3 2 6 8 8 8 8 8 8 8 6 2 3 4 2 1 2 1}
25：
[213] 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 77 85 91 93 96 100 102 103 105 106 {1 2 1 2 4 3 2 6 8 8 8 8 8 8 8 8 6 2 3 4 2 1 2 1}
26：
[229] 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 77 85 93 99 101 104 108 110 111 113 114 {1 2 1 2 4 3 2 6 8 8 8 8 8 8 8 8 8 6 2 3 4 2 1 2 1}
27:
[245] 0 1 3 4 5 8 11 15 16 25 34 43 52 61 70 79 88 97 106 107 111 114 117 118 119 121 122 {1 2 1 1 3 3 4 1 9 9 9 9 9 9 9 9 9 9 1 4 3 3 1 1 2 1}
[245] 0 1 3 4 6 10 13 15 21 29 37 45 53 61 69 77 85 93 101 107 109 112 116 118 119 121 122{1 2 1 2 4 3 2 6 8 8 8 8 8 8 8 8 8 8 6 2 3 4 2 1 2 1}
28:
[263] 0 1 3 4 5 8 11 15 16 25 34 43 52 61 70 79 88 97 106 115 116 120 123 126 127 128 130 131 {1 2 1 1 3 3 4 1 9 9 9 9 9 9 9 9 9 9 9 1 4 3 3 1 1 2 1}

比如

0,1,3,4,5,8 然后连续加6 ， 对应首尾差6(N-1)-44   （N<=22部分)
0,1,3,4, 6,10,13,15,21 然后连续加8，对应首尾差8(N-1)-86 （22<=N<=27)
0,1,3,4,5,8,11,15,16   然后连续加9，对应首尾差9(N-1)-112 (27<=N<=31)

利用上面的特性他给出了C代码构造了更大范围的解
并且给出了统计图(由于构造方法的结果种，连续整数数目总是最大数字的两倍加1，图中纵坐标代表了最大数字，而最小数字总是0) balance_stat 和验证数据正确性的代码
然后他发现加拿大滑铁卢大学有人给出了类似的结果
其中n=19比mathe找到了更好的结果，但是n=16、24结果有错误并且遗漏了n=17的最优结果。
图表中结果被提交到A302648