java - 在Java中，如何创建位图来解决 "knapsack quandary"

Question

我正在学习第一门编程类(class)，但现在我陷入了困境。基本上，我们所做的是从文本文件中获取 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

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

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

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

Answer 1

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