http://lintcode.com/en/problem/backpack-ii/

    public int backPackII(int m, int[] A, int V[]) {
        // write your code here
        
        // Brute force
        // return help(m, A, V, 0, 0, 0);
        
        int [][] max = new int [A.length + 1][m + 1];
        
        for (int[] t : max)
            Arrays.fill(t, -1);

        for (int i = 0 ; i < A.length + 1 ; i ++)
            max[i][0] = 0;

        int toReturn = 0;
        for (int i = 1 ; i < A.length + 1 ; i ++)
        {
            for (int j = 1 ; j < m + 1 ; j ++)
            {
                max[i][j] = -1;
                max[i][j] = Math.max(max[i][j], max[i - 1][j]);
                if (j - A[i - 1] >= 0 && max[i - 1][j - A[i - 1]] >= 0)
                {
                    max[i][j] = Math.max(max[i][j], max[i - 1][j - A[i - 1]] + V[i - 1]);
                }
                toReturn = Math.max(toReturn, max[i][j]);
            }
        }
        
        return toReturn;
    }

[LintCode] Backpack II