c++ - 小背包的堆栈溢出

Question

我对C++相当陌生。我已经在Coursera上的“算法工具箱”类(class)中用c++实现了小背包问题:

#include <iostream>
#include <iomanip>

using namespace std;

int get_max_index(double A[], double B[],int l)
{
    /*
    int A = array of value
    int B = array of weights
    int l = length of the array
    */
    int p,Max{0};
    for(int j=0;j<l;j++)
    {
        if((A[j]/B[j]) > Max){Max = A[j]/B[j];p = j;}
    }
    return p;
}

int main()
{
    int n,W,q,Max{0},W1{0};
    cin >> n >> W;
    double values[n],weights[n],loot{0};
    for(int i=0;i<n;i++)
    {
        cin >> values[i] >> weights[i];
    }
    for(int j=0;j<n;j++)
    {
        if(W==0){break;}
        else
        {
            q = get_max_index(values,weights,n);
            if(weights[q] <= W){W1 = weights[q];}
            else{W1 = W;}
            loot += W1 * (values[q]/weights[q]);
            W -= W1;
            weights[q] -= W1;
            if(weights[q] == 0){values[q] = 0;}
        }
    }
    cout << setprecision(4) << fixed;
    cout << loot << endl;
}

提交此代码后，我得到了堆栈溢出错误(信号11未知)。请帮助我了解为什么会发生这种情况并解决此问题。

编辑:

我已经更改了代码。我没有将get_max_index函数与动态大小的数组一起使用。这是新代码:

#include <iostream>
#include <iomanip>

using namespace std;


int main()
{
    long long int n,W,q,p,Max{0},W1{0};
    cin >> n >> W;
    long double values[n],weights[n],loot{0},VPU[n];
    for(long long int i=0;i<n;i++)
    {
        cin >> values[i] >> weights[i];
        VPU[i] = values[i] / weights[i];
    }
    for(long long int j=0;j<n;j++)
    {
        if(W==0){break;}
        else
        {
            for(long long int k=0;k<n;k++)
            {
                if(VPU[k] > Max){Max = VPU[k];p=k;}
            }
            Max = 0;
            q = p;
            if(weights[q] <= W){W1 = weights[q];}
            else{W1 = W;}
            loot += W1 * (values[q]/weights[q]);
            W -= W1;
            weights[q] -= W1;
            if(weights[q] == 0){VPU[q] = 0;}
        }
    }
    cout << setprecision(4) << fixed;
    cout << loot << endl;
}

Answer 1

C++标准不允许使用可变长度数组。因此，创建一个静态数组(分配在堆栈中)double values[n],weights[n]...的大小(在编译时未知)是不合法的(即使某些编译器可能支持)。堆栈溢出错误很可能是由于该原因(在编译时未知n，并且可能读取破坏堆栈的垃圾值)。而是尝试使用new double[n]语法在堆中分配它们。不要忘记最后释放数组。