我对下面的代码理解有问题。我已经用/comment标记了我不理解的部分。
函数'search()'被递归调用。MaxRemaining[]数组有15个元素,Size是值为15的const。
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;
在这一行中,我们检查这一列是否已经被使用过,如果是,那么我们就跳过这一列。例如,如果我们有 columnMask = 20 (10100)
和 mask
第3栏 1 << 2 = 4 (100)
那么,逻辑AND操作 columnMask & mask
如果我们为第2列设置了掩码。1 << 1 = 2 (10)
那么 columnMask & mask
将为0.Next。
auto current = search(row + 1, columnMask | mask, sum + matrix[row][column], atLeast);
在第二个参数中,我们做一个逻辑OR操作。这与加法相同。也就是说,我们确定现在使用的是列号的那一列。同样的例子,如果我们有 columnMask = 20 (10100)
和 mask
第2栏 1 << 1 = 2 (10)
那么 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;
你想掩盖 专栏 列:例如,如果列=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代表你要屏蔽的当前列。
if ((columnMask & mask) != 0)
. 记住问题规则:如果你选择了一列中的一个元素,你就不能再选择同一列中的其他元素。columnMask
存储你已经选择的列。&
是位与位运算符。所以如果 columnMask
和 mask
相同的位等于1,循环就会跳过这一列,因为它已经选择了这一列的一个元素。
columnMask | mask
. |
是bitwise-OR运算符,用于更新columnMask,即把与列元素相同的位设置为1。mask
.
if (sum + maxRemaining[row] <= atLeast) //explain this line
我无法向你解释这一行的作用,因为变量是 maxRemaining
从未分配过,可能部分代码丢失。