遍历位掩码

Question

这是对TopCoder SRM 466“彩票”问题的提交。我已经看到这种模式多次用于解决这个问题。

尼克喜欢玩彩票。单张彩票的成本就是价格。尼克具有值恰好四个纸币b1，b2，b3和b4（一些值可以是相等的）。他想知道是否有可能购买一张彩票而无需找零。换句话说，他想使用他的钞票的任何子集支付一张票的确切价格。如果可能，则返回“POSSIBLE”，否则返回“IMPOSSIBLE”（为清楚起见，所有引号）。

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 的所有可能组合（我们不必写出所有前导零，但实际上 type 总共有 32 位int）。

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];
    }
}

如果我们分解它，那么我们就有了mskwhich 代表了我们正在检查的当前组合，(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 个变量中的哪一个应该使用。