0

任务。给定金条，找出能装进一袋容量的最大黄金重量。

输入格式。输入的第一行包含一个背包的容量和金条的数量。下一行包含整数 0,1, 。. . ,−1 定义金条的重量。

约束。1≤≤104；1≤≤300；0 ≤ 0, . . . ,−1 ≤ 105。

输出格式。输出装进一个背包容量的最大重量的黄金。

我已经为这个问题实施了一个解决方案。它工作得非常好。但是在将它提交到 coursera 时，我得到了“未知信号 11”，所以我试图检查它背后的问题可能是什么。当我将变量的数据类型从二维数组更改为二维向量时，问题就解决了。我无法理解其背后的原因。请帮我解决它。

#include <iostream>
#include <vector>

using std::vector;

int optimal_weight(int W, const vector<int> &w) 
{
  int arr[w.size()+1][W+1];
  for(int i=0;i<=w.size();i++)
    for(int j=0;j<=W;j++)
    {
        if(i==0||j==0)
        arr[i][j]=0;
    }
  for(int i=0;i<=w.size();i++)
    for(int j=0;j<=W;j++)
    {
        if(i==0||j==0)
        {
            arr[i][j]=0;
            continue;
        }
        arr[i][j]=arr[i-1][j];
        if(j>=w[i-1])
        {
            arr[i][j]=std::max(arr[i][j],arr[i-1][j-w[i-1]]+w[i-1]);
        }
    }
  return arr[w.size()][W];
}

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”错误的代码但是，如果我只将 optimize_weight() 函数的第一行从

int arr[w.size()+1][W+1];

至

vector<vector<int>> arr(w.size()+ 1,vector<int>(W + 1));

然后问题就解决了！

4

0 回答 0