分段故障背包问题

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

int V[n][W];
for(int i = 0; i<=W;i++)
{
    V[0][i] = 0;
}

请注意 V 的索引从 V[0][0] 到 V[0][W-1]。您的 for 循环将尝试读取 V[0][W]。

其他地方重复同样的错误。 for 循环中的结束条件应该是 <（严格小于）而不是 <=（小于或等于）。

Answer 2

不要使用 VLA。数组的大小必须在编译时已知，否则它不是标准的 C++。这些是不可移植的编译器扩展，并引入了一些隐藏成本。
数组索引从 0 到长度 1。在你循环
```
for(int i = 0; i<=W;i++)
```
i 可以到达 W，然后 V[0][W] 越界导致段错误。您必须使用 < 而不是 <=：
```
for(int i = 0; i < W; i++)
```
n 可能应该是 4，如果它意味着表示数组的大小，std::vector 会让你的生活更轻松，因为向量知道它的大小
在这个时代，通常根本不要使用 C 风格的数组或原始指针，而是使用 std::vector。

分段故障背包问题

segmentation fault knapsackproblem

c++

knapsack-problem