时间戳

首页 > 解决方案 > 向量下标超出函数范围

c++ - 向量下标超出函数范围

问题描述

我为这个背包函数使用了一个二维向量，它不断返回超出范围的向量（第 1733 行），但向量不应该超过它们的大小并导致溢出。将 for 循环更改为 < 而不是 <= 无效。

int knapsack(int cap, vector<int>& weight, vector<int>& value, int n)
{
    vector<vector<int>> K;
    K.resize(cap, vector<int>(n));
    int i = 0;
    int j = 0;
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= cap; j++)
        {
            if (i == 0 || j == 0)
                K[i][j] = 0;
            else if (weight[i - 1] <= j)
            {
                K[i][j] = max(weight[i - 1] + K[i - 1][j - weight[i - 1]], K[i - 1][j]);
            }
            else
            {
                K[i][j] = K[i-1][j];
            }
        }
    }

    return K[i][j];
}

根据我所读到的内容，调整大小将是解决方案，但我已经使用向量大小的适当变量来做到这一点。还是我需要使用回推？

标签： c++algorithmvectorknapsack-problem

解决方案

矢量索引

当您声明K如下：

vector<vector<int>> K;
K.resize(cap, vector<int>(n));

然后向量K有长度cap，每个向量K[i]都有长度n。但是，在您的 for 循环中，我看到：

for (i = 0; i <= n; i++)
{
    for (j = 0; j <= cap; j++)
    {
        if (i == 0 || j == 0)
            K[i][j] = 0;
        ...
    }
}

看起来索引的顺序在这里是错误的，因为在if-statement 中，您可以设置K[n][0]或K[0][cap - 1]，当唯一有效的最大索引是K[cap - 1][0]andK[0][n - 1]时。

使用push_back()更安全。在这种情况下，不要忘记预留空间以避免不必要的重新分配。

循环范围

正如评论中其他人所提到的，在迭代n元素时，正确的写法是：

for (i = 0; i < cap; ++i)

所以没有'<= n'，因为它会访问'cap + 1'th元素。

在循环之后，迭代器将指向循环结束之外

一旦完成类似循环for (i = 0; i < cap; ++i)，它将增加到ivalue cap。所以最后一行：

return K[i][j];

肯定会访问超出范围的向量。你应该写这样的东西：

return K[cap - 1][n - 1];

或者，您可以使用成员函数back()访问向量的最后一个元素，并编写：

return K.back().back();

未使用的函数参数

为什么value在这个函数中根本没有使用一个参数？

断言weight具有正确的大小

访问超出范围的向量的另一个可能来源可能是该向量weight的大小不正确。您可以在代码中添加一个assert()以在调试版本中捕获此错误：

#include <cassert>
...
int knapsack(int cap, vector<int>& weight, vector<int>& value, int n)
{
    assert(weight.size() >= n - 1);
    ...

推荐阅读