c – 为什么我用这个背包问题求解器得到“未知信号11”？

任务

给定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';
}

上面的代码适用于较小的输入,但在我希望提交的平台上给出了未知信号11错误.我最好的猜测是一个可能的分段错误,但是我已经很久没有调试它了.任何帮助深表感谢！

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

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

您应该使用std :: vector容器(其默认分配器确实在堆上分配),而不是基于堆栈的分配,而不是基于堆栈的分配.因此,你会写：

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

而不是数组[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问题：

>使用更具描述性的变量名称,例如权重而不是wt和容量而不是W.我还考虑了sub_solutions_table或solutions_table而不是数组,并且还可能根据动态解决方案表的语义重命名i和j.>您实际上从不需要超过2行的解决方案表;为什么不为当前迭代分配一行,为前一次迭代分配一行,并在它们之间切换适当的指针？