Ограничение времени Превышение в KnapSack сверху вниз Подход

Question

Я написал код Java, чтобы решить следующую проблему на Spoj.com, но это дает мне «превышение лимита времени». Я не знаю, почему это происходит, я уже сделал слишком много оптимизации.

Знаменитый рюкзак проблема. Вы укладываетесь в отпуск на море, и вы собираетесь носить только один мешок с емкостью S (1 < = S < = 2000). У вас также есть N (1 < = N < = 2000) предметов, которые вы можете взять с собой на море. К сожалению, вы не можете поместить их в рюкзак, поэтому вам придется выбирать. Для каждого элемента вам заданы его размер и его значение. Вы хотите максимизировать общую стоимость всех предметов, которые вы собираетесь принести. Какова максимальная общая стоимость?

Входной

На первой строке приведены S и N. N линии следуют с двумя целыми числами в каждой строке, описывающей один из предметов. Первый номер - это размер элемента, а следующий - значение элемента.

Выход

Выведите одно целое число на один, как - общее максимальное значение от лучшего выбора элементов для вашей поездки.

Пример

Вход:

4 5 
1 8 
2 4 
3 0 
2 5 
2 3 

Выход:

Вот мой код:

import java.io.*; 
import java.util.*; 
public class Main { 


public static int max(int a,int b) 
{ 
return a>b?a:b; 
} 
    public static int dfs(int W,int nxtIdx,int[]weight,int []value,int [][]m,int N) 
    { 

     int s=Integer.MIN_VALUE; 
     if(nxtIdx>N) 
      return value[nxtIdx-1]; 
     if(m[nxtIdx][W]!=-1)return m[nxtIdx][W]; 
     for(int i=nxtIdx;i<=N;i++) 
     { 

      if((W-weight[i])>=0) 
      s=max(s,dfs(W-weight[i],i+1,weight,value,m,N)); 


     } 
     if(s!=Integer.MIN_VALUE) 
     { 

      s=s+value[nxtIdx-1]; 


     } 
     else 
     { 
      s=value[nxtIdx-1]; 

     } 
     m[nxtIdx][W]=s; 
     return s; 
    } 
    public static void main(String args[]) throws IOException 
    { 


     int value[]; 
     int weight[]; 
     int W=0,N=0; 
     BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); 
     String line[]=br.readLine().split(" "); 
     W=Integer.parseInt(line[0]); 
     N=Integer.parseInt(line[1]); 
     int m[][]=new int [N+1][W+1]; 
    value=new int [N+1]; 
    for(int i=0;i<=N;i++) 
    { 
     for(int j=0;j<=W;j++) 
      m[i][j]=-1; 

    } 
     weight=new int [N+1]; 
     value[0]=0; 
     weight[0]=0; 
     for(int i=1;i<=N;i++) 
     { 
      String input[]=br.readLine().split(" "); 

      value[i]=Integer.parseInt(input[1]); 
      weight[i]=Integer.parseInt(input[0]); 

     } 

     System.out.println(dfs(W,1,weight,value,m,N)); 



    } 
} 

Answer 1

Я не могу получить доступ к SPOJ прямо сейчас. Вы можете попробовать этот подход DP:

for(int i = 1; i <= N; ++i) { 
      for(int j = 0; j <= W; ++j) { 
       if(weight[i] > j) { 
        m[i][j] = m[i - 1][j]; 
       } 
       else { 
        m[i][j] = max(m[i-1][j], m[i-1][j-weight[i]] + value[i]); 
       } 
      } 
     }