欧拉投影问题345不能理解几行代码

提问者：小点点

欧拉投影问题345不能理解几行代码

我理解下面的代码有问题。我已在我不懂的部分加上注释//

递归调用函数“search（）”。数组有15个元素，大小是一个值为15的常量。

const unsigned int Size = 15;


unsigned short matrix[Size][Size] =
  {
    {   7,  53, 183, 439, 863, 497, 383, 563,  79, 973, 287,  63, 343, 169, 583 },
    { 627, 343, 773, 959, 943, 767, 473, 103, 699, 303, 957, 703, 583, 639, 913 },
    { 447, 283, 463,  29,  23, 487, 463, 993, 119, 883, 327, 493, 423, 159, 743 },
    { 217, 623,   3, 399, 853, 407, 103, 983,  89, 463, 290, 516, 212, 462, 350 },
    { 960, 376, 682, 962, 300, 780, 486, 502, 912, 800, 250, 346, 172, 812, 350 },
    { 870, 456, 192, 162, 593, 473, 915,  45, 989, 873, 823, 965, 425, 329, 803 },
    { 973, 965, 905, 919, 133, 673, 665, 235, 509, 613, 673, 815, 165, 992, 326 },
    { 322, 148, 972, 962, 286, 255, 941, 541, 265, 323, 925, 281, 601,  95, 973 },
    { 445, 721,  11, 525, 473,  65, 511, 164, 138, 672,  18, 428, 154, 448, 848 },
    { 414, 456, 310, 312, 798, 104, 566, 520, 302, 248, 694, 976, 430, 392, 198 },
    { 184, 829, 373, 181, 631, 101, 969, 613, 840, 740, 778, 458, 284, 760, 390 },
    { 821, 461, 843, 513,  17, 901, 711, 993, 293, 157, 274,  94, 192, 156, 574 },
    {  34, 124,   4, 878, 450, 476, 712, 914, 838, 669, 875, 299, 823, 329, 699 },
    { 815, 559, 813, 459, 522, 788, 168, 586, 966, 232, 308, 833, 251, 631, 107 },
    { 813, 883, 451, 509, 615,  77, 281, 613, 459, 205, 380, 274, 302,  35, 805 }
  };



unsigned int maxRemaining[Size];
unsigned int search(unsigned int row = 0, unsigned int columnMask = 0,unsigned int sum = 0, unsigned int atLeast = 0){
    if (row == Size)
        return sum;

    if (sum + maxRemaining[row] <= atLeast) //explain this line
        return 0;

    for (unsigned int column = 0; column < Size; column++)
    {
        auto mask = 1 << column;         //explain this line
        if ((columnMask & mask) != 0)    //explain this line
            continue;
        auto current = search(row + 1, columnMask | mask, sum + matrix[row][column], atLeast);  //explain whats with the 2nd parameter.
        if (atLeast < current)
            atLeast = current;
    }

    return atLeast;
}

共2个答案

匿名用户

我会试着解释你突出显示的线条。让我们从解释columnmask参数开始--该参数是所使用的所有列的位掩码。显然，这个掩码最初是0。下一篇:

auto mask = 1 << column;

在这行代码中，我们得到列的位掩码。下一篇:

if ((columnMask & mask) != 0)
    continue;

在这一行中，我们检查此列是否已经被使用，如果是，那么我们跳过此列。例如，如果我们有columnmask=20(10100)和mask用于第三列1<<； 2=4(100)，则逻辑与操作columnmask&；掩码将不等于0。如果我们有第二列的掩码1<<<； 1=2(10)，则columnmask&；掩码将为0。下一篇:

auto current = search(row + 1, columnMask | mask, sum + matrix[row][column], atLeast);

在第二个参数中，我们做一个逻辑或运算。这和加法是一样的。也就是说，我们确定现在使用的是具有列号的列。同样的例子，如果我们有columnmask=20(10100)和mask用于第二列1<<； 1=2(10)，则ColumnMask掩码=22(10110)。

我无法理解带有maxretain的行，因为您没有附加代码指示它包含。

匿名用户

由于函数search()的多次递归调用，调试此代码并不简单。

但是，你可以通过仔细看问题题来理解代码:

我们将矩阵的矩阵和定义为矩阵元素的最大和，其中每个元素在他的行和列中都是唯一的。例如，下面矩阵的矩阵和等于3315(=863+383+343+959+767):

  7  53 183 439 863
497 383 563  79 973
287  63 343 169 583
627 343 773 959 943
767 473 103 699 303

这个问题要求您找到最大的和，只要求每个元素是其行和列中唯一选定的元素。因此，如果函数在第一行中选择了第一列中的元素，那么对于第二行，函数必须在除第一列之外的所有列中选择一个元素。您必须将列掩码想象为由15位组成的位串，其中最低有效位是第一列，最高有效位是最后一列:

column index: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
column mask:  0  0  0  0  0  0 0 0 0 0 0 0 0 0 1

通过执行自动掩码=1<<<； column；您希望屏蔽列的第#列:例如，如果column=3，则屏蔽为:

column index: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
mask:         0  0  0  0  0  0 0 0 0 0 0 1 0 0 0

十进制的等于8。因此mask表示要屏蔽的当前列。

如果((columnMask&mask)！=0)。记住问题规则:如果选择列中的一个元素，就不能从同一列中选择其他元素。 ColumnMask存储您已经选择的列。 &是按位与运算符。因此，如果columnmask和mask的相同位等于1，则循环跳过此列，因为它已经选择了该列的一个元素。

ColumnMask掩码。是按位或运算符，用于更新columnMask，columnMask设置为1，与Mask中的位相同。

if（和+最大剩余[行]<=至少）//解释此行

我不能向您解释这一行的作用，因为变量maxretain从未被赋值，可能是部分代码丢失了。