遍历位掩码

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

对于每张纸币，您有两种选择，接受或保留（开或关）。对于 4 个音符，您可以将它们视为 4 位，如果您以二进制形式遍历 0000 到 1111，则可以遍历所有可能的选择它们的组合。

这就是位向量的作用。外循环生成所有可能的子集，内循环评估一个子集以查看它是否与所需的总和相匹配。

Answer 2

它只会生成所有 16 种可能的组合。每个组合用4位表示，1表示使用了纸币，0表示没有使用。

然后它计算组合的总和，如果总和正确，它打印 "possible".

Answer 3

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

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

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

先看这段代码：

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

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

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

让我们选择一个示例，例如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 个变量中的哪一个。

遍历位掩码

Looping over a bitmask

algorithm

bitmask