在c++中，对于较大的输入，如何使用递归中的记忆来解决没有运行时错误的0-1背包问题

Question

我正在GFG练习门户中做这个0-1背包问题。对于小的输入，代码运行良好。对于更大的输入；超过时间限制"；错误我是DP概念的新手，有人能解释一下我的错误是什么吗。我用过(递归+记忆(。

问题链接：https://practice.geeksforgeeks.org/problems/0-1-knapsack-problem0945/1#

这是代码：

int a[10005][10005]; // I have declared this globally.
int knapSack(int W, int wt[], int val[], int n) 
{ 
memset(a,-1,sizeof(a));
if (n == 0 || W == 0)
{
return 0;
}
if(a[n][W]!=-1)
{
return a[n][W];
}
if (wt[n - 1] > W)
{
a[n][W]=knapSack(W, wt, val, n - 1);  
return a[n][W];
}
if(wt[n - 1] <= W)
{
a[n][W]= max(val[n - 1]+ knapSack(W - wt[n - 1],wt, val, n - 1),knapSack(W, wt, val, n - 1));
return a[n][W];
}
}

对于较小的输入：

输入：

3//n=输入的数量

4//W行李容量

1 2 3//val[]

4 5 1//wt[]

您的输出是：3

对于较大的输入：

"超过时间限制"；

Answer 1

memset(a,-1,sizeof(a));
memset采用字节中的一个参数，因此您清除了数组的1/4(取决于您的int大小(。幸运的是，值-1变成了字节0xff，当放置在int的每个字节中时，它再次表示-1。值-1和0在这方面是特殊的。一般来说，最好使用std::fill。(尽管使用二维阵列会使情况变得复杂(

好的，您有递归调用，如：
a[n][W]=knapSack(W, wt, val, n - 1);

大概你一直需要与你已经计算过的相同的。

你需要保留一个数据库，里面有你已经计算过的所有数据。一个简单的方法是制作一个std::map，键是一个包含四个值的结构，结果就是值。用一个新函数包装实际函数(重命名(，该函数首先检查数据库，如果还不存在，则调用实际函数，将结果存储在数据库中，然后返回。

---

啊，您似乎已经通过全局数组实现了内存化。。。正如Bob在一条评论中指出的那样，memset在递归函数中，因此每次调用都会擦除保存的值。