algorithm - 遍历位掩码

Question

这是对 TopCoder SRM 466 "Lottery Ticket" problem 的提交.我已经看到此模式多次用于此问题。

Nick likes to play the lottery. The cost of a single lottery ticket is price. Nick has exactly four banknotes with values b1, b2, b3 and b4 (some of the values may be equal). He wants to know if it's possible to buy a single lottery ticket without getting any change back. In other words, he wants to pay the exact price of a ticket using any subset of his banknotes. Return "POSSIBLE" if it is possible or "IMPOSSIBLE" if it is not (all quotes for clarity).

string buy(int p, int b1, int b2, int b3, int b4) {
    int arr[] = {b1, b2, b3, b4};
    for (int msk = 0; msk < (1 << 4); ++msk) {
        int sum = 0;
        for (int i = 0; i < 4; ++i) {
            if (msk & (1 << i)) {
                sum += arr[i];
            }
        }
        if (sum == p) return "POSSIBLE";
    }
    return "IMPOSSIBLE";
}

谁能解释一下这是如何工作的？我不明白他为什么将值放入数组并使用两个嵌套的 for 循环进行循环。

Answer 1

这个问题可以扩展到任意数量的钞票，但让我们看一下这个例子。

这个解决方案的想法是使用蛮力方法来解决问题。这意味着我将尝试所有可能的解决方案，如果其中一个有效，那么结果是肯定的。

在这种情况下，工作解决方案意味着我选择的钞票总和等于 p。

我们先来看这段代码:

for (int msk = 0; msk < (1 << 4); ++msk)

这表示我要遍历从 0 到 2^4-1 的所有数字，即 0-15。

如果你用二进制表示法写这些数字，你会注意到它们涵盖了长度为 4 的所有可能组合(我们不必写所有前导零，但对于类型 int 实际上总共有 32 位) .

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

让我们选择一个示例，例如1010 。这意味着我将选择位置 1 和 3 的数字(从右到左从 0 开始)。然后我将检查这两个数字的总和是否等于 p。

下一个 for 循环对位置为 1 的所有数字求和:

for (int i = 0; i < 4; ++i) {
    if (msk & (1 << i)) {
        sum += arr[i];
    }
}

如果我们分解它，那么我们有 msk 代表我们正在检查的当前组合和 (1 << i) 这只是左移位操作，给我们 2^i ，或二进制表示法:

0001 = 1 << 0
0010 = 1 << 1
0100 = 1 << 2
1000 = 1 << 3

注意:(1 << i) 在括号内，因为 & 具有更高的优先级，在这种情况下我们不希望这样。

如果您在两个整数之间使用 & 运算符，您将得到按位运算，例如

1010 & 1000 = 1000   // this is greater than 0
1010 & 0100 = 0000   // this is equal to 0

因此 if (msk & (1 << i)) 仅适用于当前组合中具有 1 的位置，即 msk 。

我希望这也解释了为什么他将值放在数组中的原因 - 这是因为他想为每张钞票分配一个索引，然后如果掩码的位置为 1，则使用该钞票，而不是找出哪个应使用 4 个变量。