函数未 returning/Program 退出

Question

我正在为背包问题的动态解决方案编写代码，从文件中读取值、重量等。写完背包功能的代码后，我尝试测试时似乎不会 return 结果是 returned.

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>

using namespace std;

//knapsack here
int knapsack(int cap, int weight[], int value[], int n)
{
    int** K = new int* [n + 1];
    int j = 0;
    int l = 0;
    for (int i = 0; i < n + 1; i++)
    {
        K[i] = new int[cap + 1];
    }
    for (j = 0; j <= n; j++)
    {
        for (l = 0; l <= cap; l++)
        {
            if (j == 0 || l == 0)
                K[j][l] = 0;
            else if (weight[j - 1] <= l)
            {
                K[j][l] = max(weight[j - 1] + K[j - 1][l - weight[j - 1]], K[j - 1][l]);
            }
            else
            {
                K[j][l] = K[j - 1][l];
            }
        }
    }

    return K[j][l]; <--- Exception thrown
}

int main(void)
{
    string filename;
    ifstream infile;
    int capacity = 0;
    int items = 0;

    //Get input file from user and open

    cout << "Enter the file name: ";
    cin >> filename;

    infile.open(filename);

    //Get capacity and number of items
    infile >> capacity >> items;

    //Initialize arrays
    int* w = new int[items];
    int* v = new int[items];

    //Read values from file into arrays
    for (int i = 0; i < items; i++)
    {
        infile >> w[i];
        infile >> v[i];
    }

    //Solution Table
    cout << endl << endl << endl;
    cout << "Solution Table:" << endl;

    //Testing purposes
    cout << knapsack(capacity, w, v, items) << endl << "Test";

    infile.close();

    return 0;

}

在 main 中打印的所有内容都将打印到最后的 cout（在解决方案 Table: 行打印之后）。然后程序将暂停片刻并退出并返回错误代码 (C:\Users\Me\source\repos\Project3\Debug\Project3.exe (process 3028) exited with code -1073741819)。我还没有想出从函数中获取 return 的方法，而退出是我也无法弄清楚为什么会发生的事情。

编辑：在使用调试器时，当运行通过 return 上的背包函数时抛出异常：

在 Project3.exe 中的 0x006BB128 处抛出异常：0xC0000005：访问冲突读取位置 0xFDFDFE0D

Answer 1

C 风格的字符串可能会导致问题。它们很难维护和跟踪。我在这里支持 Jesper 的想法。

此外，我没有看到您在使用完会造成内存泄漏的指针后释放内存。

Answer 2


    int** K = new int* [n + 1];
    // ...
        K[i] = new int[cap + 1];
    // ...
    for (j = 0; j <= n; j++)
    {
        for (l = 0; l <= cap; l++)
        {
            // ...
        }
    }
    // j == n + 1
    // l == cap + 1
    return K[j][l]; <--- Exception thrown because of out of bounds access to K

K 是一个长度为 n + 1 的数组，这意味着使用从 O 到（含）n 的索引访问其元素。 n + 1 是越界访问。在（外部）for 循环的末尾，变量 j 是 n + 1。您在内部循环和第二个 operator[].

中犯了同样的错误

话虽如此，如果您：

摒弃“二维数组”的想法。这些指向数组的指针数组很难处理，并且会严重影响性能（弄乱内存位置）。它们（可能）仅在“完整”数组（例如 2D table 扁平化为单个数组）太大而无法可靠地成功分配时有用。
使用std::vector。使用原始数组真的没有意义。除了学习。在这种情况下：delete[] 您分配的内存！
Why is "using namespace std;" considered bad practice?

函数未 returning/Program 退出

Function not returning/Program exiting

c++

algorithm

knapsack-problem