SIGKILL在spoj-LKS

Question

提交解決方案時，它顯示一個運行時錯誤SIGKILL。我不知道爲什麼！請幫忙...！！我不打算討論TLE，我只是想知道SIGKILL的原因是什麼。之後，你可能會建議我更快地解決這個問題的程序。請幫忙，我也一直在堅持這個問題。很長一段時間，但我無法找到運行時錯誤是如何發生的。 這裏是我的代碼::

#include<stdio.h>

//#define max(a,b) a>b?a:b 
int max (int a,int b){ 
    if (a>b) 
     return a; 
    else return b; 

} 
int V[500]; 
int W[500]; 
int F[501][1000001]; 



int knapsack(int n,int cap){ 
    if (n==0 || cap==0){ 
     F[n][cap]=0; 
     return 0; 
    } 
    else if (cap<1000001){ 
     if (F[n][cap]!=0) 
      return F[n][cap]; 
     else { 
      if (W[n-1]>cap){ 
       F[n][cap]=knapsack(n-1,cap); 
      } 
      else { 
       F[n][cap]=max(V[n-1]+knapsack(n-1,cap-W[n-1]),knapsack(n-1,cap)); 
      } 

      return F[n][cap]; 
     } 
    } 
    else { 
     if (W[n-1]>cap){ 
      return knapsack(n-1,cap); 
      } 
     else { 
      return max(V[n-1]+knapsack(n-1,cap-W[n-1]),knapsack(n-1,cap)); 
     } 

    } 

} 

main() { 
    int k,n,i; 
    scanf("%d %d",&k,&n); 

    for (i =0 ;i<n ;i++){ 
     scanf("%d %d",&V[i],&W[i]); 

    } 

    printf("%d\n",knapsack(n,k)); 

} 

Answer 1

原因SIGKILL是你的數組F [501] [1000001]

這是因爲全局變量是從堆中獲得的內存。 現在Spoj上LKS的內存限制爲1536 MB，相當於1.6E9字節。 因爲int的長度是4個字節，所以int數組的最大大小可以大約爲4E8，並且您聲明瞭5E8大小的int數組。所以減少你的數組大小可以讓你擺脫SIGKILL。

要解決此問題，您需要做的是爲2行的dp創建一個數組，然後計算答案。

int dp[2][2000001]; 

我希望這會有所幫助。 :)