1

我正在上我的第一门编程课程，现在我很困惑。基本上，我们所做的是从文本文件（在第一行代码）中获取 16 个值，在第二行代码中只有一个值。我们将这 16 个值读入一个数组，并将第二行值设置为目标。我对那部分没有问题。

但是，我遇到麻烦的地方是创建一个位图来测试 16 个值的每个可能的子集，它等于目标数。

IE，假设我们有这些数字：

12   15   20   4   3   10   17   12   24   21   19   33   27   11   25   32

然后我们将每个值对应一个位图

 0    1    1   0   0    0    0    1    1    1    0    1    0    0    1    0

那么我们只接受以“1”为谓词的值

     15   20                     12   24   21        33             25

然后我们测试该子集以查看它是否等于“目标”数。

我们只允许在问题中使用一个数组，并且我们不允许使用数学类（还没有得到它）​​。

我理解这个概念，我知道我需要实现移位运算符和逻辑&符号，但我真的很茫然。我非常沮丧，我只是想知道是否有人可以给我任何提示。

4

5 回答 5

0

解决这个问题有几个步骤。首先，您需要枚举所有可能的位图。正如其他人指出的那样，您可以通过将整数从 0 增加到 2^n - 1 来轻松做到这一点。

一旦你有了它，你就可以遍历所有可能的位图，你只需要一种方法来获取该位图并将其“应用”到一个数组中，以生成由该图表示的所有索引处的元素之和。以下方法是如何执行此操作的示例：

private static int bitmapSum(int[] input, int bitmap) {
    // a variable for holding the running total
    int sum = 0;

    // iterate over each element in our array
    // adding only the values specified by the bitmap
    for (int i = 0; i < input.length; i++) {
        int mask = 1 << i;
        if ((bitmap & mask) != 0) {
            // If the index is part of the bitmap, add it to the total;
            sum += input[i];
        }
    }

    return sum;
}

此函数将采用一个整数数组和一个位图（表示为整数）并返回数组中其索引存在于掩码中的所有元素的总和。

此功能的关键是能够确定给定索引是否确实在位图中。这是通过首先为所需索引创建一个位掩码，然后将该掩码应用于位图以测试该值是否已设置来实现的。

基本上我们想要构建一个整数，其中只有一位被设置，其他所有位都为零。然后，我们可以将该掩码与位图按位与，并通过将结果与 0 进行比较来测试是否设置了特定位置。

假设我们有一个 8 位映射，如下所示：

map:       1 0 0 1 1 1 0 1
           ---------------
indexes:   7 6 5 4 3 2 1 0

要测试索引 4 的值，我们需要一个如下所示的位掩码：

mask:      0 0 0 1 0 0 0 0
           ---------------
indexes:   7 6 5 4 3 2 1 0

要构建掩码，我们只需从 1 开始并将其移动 N：

1:            0 0 0 0 0 0 0 1
shift by 1:   0 0 0 0 0 0 1 0
shift by 2:   0 0 0 0 0 1 0 0
shift by 3:   0 0 0 0 1 0 0 0
shift by 4:   0 0 0 1 0 0 0 0

一旦我们有了这个，我们就可以将掩码应用于地图并查看是否设置了值：

map:             1 0 0 1 1 1 0 1
mask:            0 0 0 1 0 0 0 0
                 ---------------
result of AND:   0 0 0 1 0 0 0 0

由于结果是 != 0 我们可以知道索引 4 包含在地图中。

于 2012-02-06T22:44:40.780 回答
0

因此，任务是一种算法，给定一组A非负数和一个目标值k，确定是否存在A其元素之和为的子集k。

我会使用对 A 的归纳来解决这个问题，跟踪哪些数字 <= k 是迄今为止处理的元素集的子集的总和。那是：

boolean[] reachable = new boolean[k+1];
reachable[0] = true;
for (int a : A) {
    // compute the new reachable
    // hint: what's the relationship between subsets of S and S \/ {a} ?
}
return reachable[k];

从数学上讲，位图是将一系列数字映射到 {0, 1} 的函数。Aboolean[]将数组索引映射到布尔值。所以可以称为boolean[]位图。

使用 a 的一个缺点boolean[]是您必须单独处理每个数组元素。相反，可以使用 long 保存 64 位，并使用位移和掩码操作一次处理 64 个“数组”元素。但是这种微优化很容易出错并且相当复杂，因此通常不会在应该可靠和可维护的代码中完成。

于 2012-02-06T22:10:15.987 回答
0

我认为你需要这样的东西：

public boolean equalsTarget( int bitmap, int [] numbers, int target ) {
  int sum = 0; // this is the variable we're storing the running sum of our numbers
  int mask = 1; // this is the bitmask that we're using to query the bitmap
  for( int i = 0; i < numbers.length; i++ ) { // for each number in our array
    if( bitmap & mask > 0 ) { // test if the ith bit is 1
        sum += numbers[ i ]; // and add the ith number to the sum if it is
    } 
    mask <<= 1; // shift the mask bit left by 1
  }
  return sum == target; //if the sum equals the target, this bitmap is a match
}

您的其余代码相当简单，您只需将位图 (1..65535) 的每个可能值输入此方法并根据结果进行操作。

Ps：请确保您完全理解解决方案，而不仅仅是复制它，否则您只是在欺骗自己。:)

Pps：int在这种情况下使用是有效的，因为int它是 32 位宽，我们只需要 16 位。尽管如果您需要所有位，请小心按位运算，因为所有原始整数类型（字节、短、整数、长）都在 Java 中签名.

于 2012-02-06T22:23:20.163 回答
0

要在 int 内生成所有可能的位模式，因此由该位图定义的所有可能子集只需要您从 1 开始 int 并不断将其递增到 unsigned short int 可以容纳的最高可能值（全为 1）。在每个内部循环结束时，将总和与目标进行比较。如果匹配，您将得到一个解决方案子集 - 将其打印出来。如果没有，请尝试下一个子集。有人可以帮助解释如何去做吗？我理解这个概念，但缺乏如何实现它的知识。

于 2012-02-06T21:46:32.997 回答
0

好的，所以您可以使用一个数组。据推测，该数组包含第一组数据。所以你的方法不需要有任何额外的数组。

在这种情况下，位向量只是一个心理模型构造。这个想法是这样的：如果您尝试所有可能的组合（注意，不是排列），那么您将找到最接近目标的总和。所以假设你有 N 个数字。这意味着您有2^N可能的组合。

位向量方法是用 to 对每个组合进行编号0，2^N - 1然后尝试每个组合。

假设数组中的数字少于 32 个，则基本上有一个像这样的外部循环：

int numberOfCombinations = (1 << numbers.length - 1) - 1;
for (int i = 0; i < numberOfCombinations; ++i) { ... }

对于 的每个值i，您需要检查 中的每个数字numbers，根据 的移位和位掩码决定添加或跳过i。

于 2012-02-06T22:02:39.703 回答