c++ - 为什么我用这个背包问题求解器得到 "unknown signal 11"？

Question

任务

给定 n 根金条，找出容量 W 的袋子中最大重量的金条

输入

第一行包含背包的容量W和金条的数量n。下一行包含n个整数

输出

一个容量为W的背包所能容纳的最大黄金重量。

约束

1 <= W <= 10000; 1<= n <= 300； 0 <= w0, w1, w2, ..., w(n-1) <= 100000

代码

#include <iostream>
#include <vector>
using std::vector;

int optimal_weight(int W, vector<int> w) {
  int n = w.size() + 1;
  int wt = W + 1;
  int array [n][wt];
  int val = 0;

  for(int i = 0; i < wt; i++) array [0][i] = 0;
  for(int i = 0; i < n; i++) array [i][0] = 0;

  for(int i = 1; i< n; i++) {
    for(int j = 1; j < wt; j++ ){
      array[i][j] = array [i-1][j];
      if (w[i-1] <= j) {
        val = array[i-1][j - w[i-1]] + w[i-1];
        if(array[i][j] < val) array[i][j] = val;
      }
    }
  }

  //printing the grid
  // for(int i=0; i < n; i++) {
  //   for(int j=0; j < wt; j++) {
  //     cout<<array[i][j]<<" ";
  //   }
  //   cout<<endl;
  // }
  // cout<<endl;

  return array [n-1][wt-1];
}

int main() {
  int n, W;
  std::cin >> W >> n;
  vector<int> w(n);
  for (int i = 0; i < n; i++) {
    std::cin >> w[i];
  }
  std::cout << optimal_weight(W, w) << '\n';
}

上面的代码适用于较小的输入，但在我希望提交的平台上会出现 unknown signal 11 错误。我最好的猜测是可能存在段错误，但我已经有一段时间无法调试它了。非常感谢任何帮助!

Answer 1

首先请注意，您的代码不起作用。也就是说，当您严格遵守 C++ 语言标准时，它不会编译，如 C++ does not support variable-length arrays . (正如@Evg 在评论中指出的那样；一些编译器将其作为扩展提供。)

将它们排除在 C++ 之外的主要原因可能是您遇到较大问题的原因:stack overflows 的危险，与该网站同名(正如@huseyinturgulbuyukisik 在评论中指出的那样)。可变长度数组分配在堆栈上，其大小是有限的。当您超过它时，您可能会尝试写入未分配给您的进程的内存段，从而触发 Linux 信号 11，也称为 SIGSEGV - segmentation violation信号。

而不是基于堆栈的分配，你应该allocate your memory on the heap .一种直接的方法是使用 std::vector容器(其默认分配器确实在堆上分配)。因此，你会写:

 std::vector<int> vec(n * wt);

而不是 array[i][j]你会用 vec[i * wt + j] .

现在，这不如使用 array[x][y] 方便;为了更加方便，您可以编写一个辅助 lambda 来访问各个元素，例如

auto array_element = [&vec, wt](int x, int y) { return vec[x * wt + y]; }

有了这个 lambda 函数，您现在可以编写诸如 array_element(i,j) = array_element(i-1,j); 之类的语句

或使用多维容器(std::vector<std::vector<int>> 可以，但恕我直言，它既丑陋又浪费资源；不幸的是，标准库没有与之等效的单分配多维容器)。

---

其他建议，与信号 11 问题的解决方案无关:

• 使用更具描述性的变量名称，例如weight而不是 wt和 capacity而不是 W .我也会考虑 sub_solutions_table或 solutions_table而不是 array , 也可能重命名 i和 j根据动态解表的语义。
• 您实际上永远不需要超过 2 行的解决方案表；为什么不为当前迭代分配一行，为上一次迭代分配一行，并让适当的指针在它们之间切换？