c - 0 1 背包的算法实现的复杂度是多少？

Question

在代码的递归版本中，我使用了一个查找表来避免重新计算。但我无法弄清楚它是否比自下而上的方法更好。那么它更好吗？我试过用 n = 20 来解决，但没有出现堆栈溢出错误。那么，这种方法好吗？而且，如果我尝试在同一代码中使用 W = 90 而所有其他输入保持不变(如以下代码所示)，我会得到一些垃圾值作为答案，为什么？
我知道用最大值全局声明 look 数组不是好的方法(内存浪费)。我可以改为在大小为 n x W+1 的主函数中动态声明它，我试过了。但是当我试图在函数中传递它时，它(Dev-C++)给了我一个警告，从不兼容的指针类型传递 arg 并首先忽略警告并运行程序我在输出中没有得到任何结果。可能是什么原因. PS:我是初学者，非常感谢。

  #include<stdio.h>
  #define MAXN 20
  #define MAXW 100

  int look[MAXN][MAXW];

  int max(int a, int b){
         return (a > b)? a : b; 
  }


 int knapSack(int W, int wt[], int val[], int n){

      if (n == -1 || W == 0)
          return 0;
      if(look[n][W]!=-1)
          return look[n][W];

      if (wt[n] > W){
          look[n-1][W]=knapSack(W, wt, val, n-1);
          look[n][W]=look[n-1][W];
      }

      else   
           look[n][W]=max( val[n] + knapSack(W-wt[n], wt, val, n-1),knapSack(W, wt, val, n-1));

      return look[n][W];
  }

  int main(){

      int val[] = {7,4,5,1};
      int wt[] = {5,4,3,1};
      int i,j,W = 7;
      int n = sizeof(val)/sizeof(val[0]);

      for(i=0;i<n;i++)
          for(j=0;j<=W;j++)look[i][j]=-1; 
              printf("%d", knapSack(W, wt, val, n-1));
      return 0;
 }

Answer 1

I get some garbage value as the answer, why?

查看函数 knapSack() 中的初始语句:

      if(look[n][W]!=-1)
          return look[n][W];
      if (n == -1 || W == 0)
          return 0;

可以通过递归调用函数，n 为 -1，您可以在第二个 if 语句中满足这一点，但为时已晚，因为在第一个 if 条件你已经访问了未定义的值 look[-1][W]。您可能想要颠倒这两个语句的顺序。