为什么我用这个背包问题求解器得到"未知信号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++不支持可变长度数组.(正如@Evg在评论中所指出的;一些编译器将此作为扩展提供.)

从C++中排除这些问题的主要原因可能就是为什么你遇到更大问题规模的问题:堆栈溢出的危险,这个网站的同名(正如@huseyinturgulbuyukisik在评论中指出的那样).可变长度数组在堆栈上分配,其大小有限.当您超过它时,您可能会尝试写入未分配给您的进程的内存段,从而触发Linux信号11,也称为SIGSEGV - 分段违规信号.

您应该在堆上分配内存,而不是基于堆栈的分配.一种直接的方法是使用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行的解决方案表; 为什么不为当前迭代分配一行,为前一次迭代分配一行,并在它们之间切换适当的指针？