java - 创建并填充可变大小的二进制真值表

Question

我正在尝试通过蛮力解决 0/1 背包问题。最简单(看起来)的方法是设置一个二维矩阵，其中 1 和 0 分别表示背包中存在和不存在。参数将是项目数(即:列)，因此行应为 2^numOfItems。但是由于项目的数量不是常数，我想不出如何填充矩阵。有人告诉我位移位会起作用，但我不明白它是如何起作用的。有人可以指出我正确的方向吗？

编辑:我所说的真值表是指其中之一的“A”部分:http://www.johnloomis.org/ece314/notes/devices/binary_to_BCD/bcd03.png

Answer 1

您不必将所有位序列存储在矩阵中，这是不必要的，而且会浪费太多内存。您可以简单地使用一个整数来表示当前集合。整数将从 0 到 2^n-1，其中 n 是您可以选择的元素数。这是基本思想。

int max = (1 << n);
for(int set = 0; set < max; set++)
{
    for(int e = 0; e < n; e++)
    {
        if((set & (1 << e)) != 0)
           //eth bit is 1 means that the eth item is in our set
        else
           // eth element will not be put in the knapsack
    }
}

该算法依赖于逻辑左移。 (1 << n)意味着我们将通过在数字的右侧填充零来向左移动 1, n 个位置。因此，例如，如果我们将 1 表示为 8 位数字 00000001、(1 << 1) == 00000010、(1 << 2) == 00000100 等。按位与运算符是一个接受两个参数的运算符, 和 "ands"每两个具有相同索引的位。因此，如果我们有 2 个长度为 n 的位串，位 0 将与位 0 相加，位 1 与位 1 相加，等等。当且仅当两位均为 1 时 & 的输出为 1，否则为 0。为什么这个有用？？我们需要它来测试位。例如，假设我们有一些表示为位串的集合，我们想确定位集中的第 i 个位是 1 还是 0。我们可以通过使用左移运算然后按位与运算来做到这一点。

例子

设置 = 00101000 我们要测试 Set(3)(记住最右边的位是位 0) 我们可以通过将 1 向左移动 3 个位置来做到这一点，因此它变成 00001000。然后我们将移动后的 1 与集合“相加”

00101000
         &
00001000
---------
00001000

如您所见，如果我要测试的位是 1，则 & 的输出将不为零，否则为零。