0

我有一个任务是解决旅行推销员问题。我不会撒谎，我现在正在做的部分实际上我并不完全理解他们在问，如果我奇怪地表达这个问题，很抱歉。我有点明白，但不完全。

我们正在计算推销员的大致距离。我们需要创建一个二维数组，我相信比特集？无论如何以二进制形式存储值。0代表未访问过，1代表已访问过。

我们得到了一个有很大帮助的算法，如果这里有人可以帮助第一步，我应该能够完成它：

Create memoisation table [N][(1 << N)]

（其中 N = 城市数）。我知道 1 << N 意味着将城市数量（例如 5）转换为二进制，然后将集合向左移动一个位置。

我的主要问题是：

  1. 将 N 转换为二进制（我认为这是我需要做的？）
  2. 将集合向左移动一位
  3. 实际上创建这些大小的二维数组......

我在这里可能是错的，事实上这很可能......任何帮助表示赞赏，谢谢！

4

1 回答 1

0

这是一般规则“<<”运算符表示左移，“>>”表示右移。将任何数字右移 1 相当于除以 2，将任何数字左移 2 相当于乘以 2。例如，假设一个数字 7（二进制 111）。因此 7 << 1 将变为 1110 即 7 * 2 = 14 并且 7 >> 1 将变为 11 即 7 / 2 = 3 。

因此，对于将数字 N 转换为二进制的位集数组的算法是

  1. N mod 2（如果将 N 除以 2，则取余数）
  2. 将余数存储在集合中（即 List、Array、Stack ）
  3. 将 N 除以 2
  4. 如果 N/2 >1 从步骤 1 重复 N/2
  5. 否则反转数组，你就有了你的位集。

将集合向左移动到一个，如果你的意思是左移一个，你可以通过 N<<1

这就是在 C++ 中创建二维数组的方式

[变量类型] TwoDimensionalArray[size][size];

对于这个问题，尽管我相信您可能想阅读有关 C++ bitset 的信息，并且您可以使用 bitset 轻松实现它。为此，您只需弄清楚要使用的位集的大小。例如，如果 N 的最大值是 15，那么您需要的 bitset 大小为 4。因为使用 4 位，您可以表示的最大数字是 15（二进制 1111）。希望这可以帮助。

于 2013-06-03T04:35:29.023 回答