我在理解下面的代码时遇到问题。我已经用//comment 标记了我不明白的部分
函数 'search((' 被递归调用。MaxRemaining[] 数组有 15 个元素，Size 是一个值为 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;
}
我将尝试解释您突出显示的行。让我们从解释columnMask参数开始 - 这个参数是所有使用的列的位掩码。显然，此掩码最初为 0。下一个：
auto mask = 1 << column;
在这一行代码中，我们得到了列的位掩码。下一个：
if ((columnMask & mask) != 0)
continue;
在这一行中，我们检查此列是否已使用，如果是，则跳过此列。例如，如果我们对第 3 列1 << 2 = 4 (100)有columnMask = 20 (10100)和mask，则逻辑 AND 运算columnMask & mask将不等于 0。如果我们有掩码 第二列1 << 1 = 2 (10)，那么columnMask & mask将为 0。 下一个：
auto current = search(row + 1, columnMask | mask, sum + matrix[row][column], atLeast);
在第二个参数中，我们执行逻辑 OR 操作。这与加法相同。也就是说，我们确定现在使用带有列号的列。同样的例子，如果我们有第二列1 << 1 = 2 (10)的columnMask = 20 (10100)和mask，则columnMask | mask = 22 (10110).
下一个：
if (sum + maxRemaining[row] <= atLeast)
return 0;
据我了解，maxRemaining[row]包含从row到Size-1列中最大元素的总和，包括 和 。然后这个条件有助于加快算法的操作，因为如果sum + maxRemaining[row]小于当前的最佳解决方案(atLeast(，那么继续这个递归分支是没有意义的，因此返回 0，这基本上丢弃了这个递归分支。
由于函数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
- 该问题要求您仅通过每个元素是其行和列中唯一选定的元素来查找最大总和。因此，如果在第一行中函数选择第一列中的元素，则对于第二行，函数必须在除第一列之外的所有列中选择一个元素。您必须将
column mask想象为由 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
通过执行auto mask = 1 << column;，您希望屏蔽第 1 列：例如，如果 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。因此，掩码表示要遮罩的当前列。
if ((columnMask & mask) != 0).请记住问题规则：如果在列中选择一个元素，则无法从同一列中选择其他元素。columnMask存储已选择的列。&是按位 AND 运算符。因此，如果columnMask和mask具有等于 1 的相同位，则循环将跳过此列，因为它已经选择了该列的元素。columnMask | mask.|是按位 OR 运算符，用于更新 columnMask，即设置为 1 与mask中的位相同。if (sum + maxRemaining[row] <= atLeast) //explain this line
我无法向您解释这一行的作用，因为变量maxRemaining从未分配过，也许缺少部分代码。