在Java中，如何创建位图来解决“背包困境”？

Question

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

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

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

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

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

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

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

Answer 1

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

Answer 2

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

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

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

假设数组中的数字少于 32 个，则本质上有一个如下所示的外循环：

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

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

Answer 3

因此，任务是设计一种算法，在给定一组非负数 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} 的函数。 boolean[] 将数组索引映射到布尔值。因此，我们可以将 boolean[] 称为位图。

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

Answer 4

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

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 位。请小心按位运算，但如果您需要所有位，因为所有原始整数类型（byte、short、int、long）在 Java 中都是有符号的。

Answer 5

解决这个问题有几个步骤。首先，您需要枚举所有可能的位图。正如其他人指出的那样，您可以通过将整数从 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 已包含在内在地图中。