通过自顶向下的方法超过KnapSack的时间限制

我已经编写了Java代码来解决Spoj.com上的以下问题，但它给了我“超出时间限制”。我不知道为什么会发生，我已经做了太多的优化。通过自顶向下的方法超过KnapSack的时间限制

着名的背包问题。您正在打包海边度假，并且您将只携带一个容量为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)); 



    } 
}

来源

2017-02-05 Beer Gupta

你需要记住所有的递归调用。 –

我已经这么做了 –

你背包的做法是不正确的。 –

我现在无法访问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]); 
       } 
      } 
     }

来源

2017-02-05 18:28:48

当然，让我试试 –

现在它说错了ans，嘿，我的逻辑是好的我认为，在你的情况res = max（res，s）那么为什么你回到s，你应该返回“res” –

https://www.hackerearth.com/submission/7118667/ 请在不同的平台上看一下这个提交具有相同的概念 –

通过自顶向下的方法超过KnapSack的时间限制

回答

相关问题