Проблема с рюкзаком, визуальные проблемы студии

Question

Я реализовал решение динамического программирования для известной задачи о ранце.Самое смешное в этом то, что visual studio пока не позволяет компилировать мой код, когда я копирую и вставляю свой код в cpp.sh, он работает без ошибок.

На данный момент это то, чем я являюсьполучить в визуальной студии за ошибки:

    Unhandled exception at 0x0FADED76 (ucrtbased.dll) in Practice.exe: An invalid 
parameter was passed to a function that considers invalid parameters fatal.

Это происходит в строке 10, то есть dp[i][j] = 0.Я не уверен, как решить эту проблему, и вообще я заметил, что visual studio может быть особенно плаксивой.

Вот мой код:

#include <iostream>
#include <vector>
#include <algorithm>

int maxKnapSack(std::vector<int>& v, std::vector<int>& w, int capacity) {
    std::vector<std::vector<int>> dp(capacity + 1, std::vector<int>(v.size() + 1));
    for (int i = 0; i <= v.size(); i++) {
        for (int j = 0; j <= capacity; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            }
            else if (j - w[i - 1] >= 0) {
                dp[i][j] = std::max(v[i-1] + dp[i - 1][j - w[i-1]], dp[i - 1][j]);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[v.size()][capacity];
}


int main() {

    std::vector<int> v = { 10, 4, 7 };
    std::vector<int> w = { 4, 2, 3 };
    int capacity = 5;

    std::cout << "The maximum I can get is " << maxKnapSack(v, w, capacity) << "\n";

    std::cin.get();
}

Answer 1

Ваш вектор dp содержит 6 элементов, каждый элемент является вектором 4 элементов.Это эквивалентно определению массива int dp[6][4].

Ваш внешний цикл цикла от 0 до 4 (включительно) и внутренний цикл цикла от 0 до 6 (включительно).Это означает, что вы будете использовать индекс вне границ во вложенном (внутреннем) векторе.

Ваши циклы должны быть наоборот с их пределами.Или ваш вектор dp должен быть определен с переключенными размерами.

---

Ваши условия во внутреннем цикле также неверны.Условие i == 0 || j == 0 будет ложно , если, например, i == 0 и j != 0.Это приведет к тому, что вы будете использовать отрицательные индексы из-за i - 1.Это также выходит за пределы и снова приводит к неопределенному поведению .

Вам необходимо убедиться, что else if происходит только тогда, когда i > 0 и j - w[i-1] > 0.И else только при i > 0.