背包问题，视觉工作室问题

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.我不确定如何解决这个问题，总的来说，我注意到视觉工作室可能特别抱怨。

这是我的代码：

#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时才发生。只有当i > 0时，else.