c++ - 段错误背包问题

Question

我用 C++ 编写了这个背包问题解决方案，但是当我运行它时，它给了我段错误
我已经尝试了一切，我的编译器总是会给我段错误错误。

#include<iostream>
#include<algorithm>

int knapsack(int v[],int w[],int n,int W)
{
    int V[n][W];
    for(int i = 0; i<=W;i++)
    {
        V[0][i] = 0;
    }
    for(int i = 0; i <= n; i++){
        for(int j = 1; j<=W; j++)
        {
            if(w[i]<=W)
            {
                V[i][j] = std::max(V[i-1][j], v[i]+V[i-1][j-w[i]]);
            }
            else
            {
                V[i][j] = V[i-1][j];
            }

        }
    }
    return V[n][W];
}

int main()
{
    int v[4] = {10,40,30,50};
    int w[4] = {5,4,6,3};
    int n = 3;
    int W = 10;

    std::cout<<"item value:"<<knapsack(v,w,n,W);
}

Answer 1

不要使用 VLA。数组的大小必须在编译时知道，否则它不是标准的 C++。这些是不可移植的编译器扩展，并引入了一些隐藏的成本。

数组索引从 0 到 length-1。在你循环中

for(int i = 0; i<=W;i++)

i可以联系W ，然后 V[0][W]越界导致段错误。您必须使用 <而不是 <= :

for(int i = 0; i < W; i++)

n应该是 4，如果它是为了表示数组的大小，一个 std::vector会让你的生活更轻松，因为 vector 知道它的大小

一般来说，在这个时代根本不要使用 C 风格的数组或原始指针，使用 std::vector反而。