algorithm - 通过自上而下的方法在 KnapSack 中超过时间限制

Question

我已经编写了 Java 代码来解决 Spoj.com 上的以下问题，但它给了我“超出时间限制”。我不知道为什么会这样，我已经做了太多优化。

The famous knapsack problem. You are packing for a vacation on the sea side and you are going to carry only one bag with capacity S (1 <= S <= 2000). You also have N (1<= N <= 2000) items that you might want to take with you to the sea side. Unfortunately you can not fit all of them in the knapsack so you will have to choose. For each item you are given its size and its value. You want to maximize the total value of all the items you are going to bring. What is this maximum total value?

Input

On the first line you are given S and N. N lines follow with two integers on each line describing one of your items. The first number is the size of the item and the next is the value of the item.

Output

You should output a single integer on one like - the total maximum value from the best choice of items for your trip.

Example

Input:

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

Output:

13

这是我的代码:

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]);
                }
            }
        }