Task. Given gold bars, find the maximum weight of gold that fits into a bag of capacity .
Input Format. The first line of the input contains the capacity of a knapsack and the number of bars of gold. The next line contains integers 0,1, . . . ,−1 defining the weights of the bars of gold.
Constraints. 1 ≤ ≤ 104; 1 ≤ ≤ 300; 0 ≤ 0, . . . ,−1 ≤ 105.
Output Format. Output the maximum weight of gold that fits into a knapsack of capacity .
I have implemented a solution for this problem. It worked really well. But while submitting it to coursera, i got "unknown signal 11" so I tried to check what may be the problem behind it. And when I changed the datatype of one the variables from 2-D array to 2-D vector, the problem got resolved. I am not able to understand the reason behind it. Please help me to tackle it.
#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';
}
This is the code that throws "Unknown Signal 11" error However, if I only change the 1st line of the optimal_weight() function from
int arr[w.size()+1][W+1];
To
vector<vector<int>> arr(w.size()+ 1,vector<int>(W + 1));
Then the problem gets resolved !