(UVA) Divisible Group Sums - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1557

The solution below used the concept of Knapsack, related to Dynamic Programming, to solve this problem.


import java.io.*;
import java.util.*;

class Main {
    public int[] numbers;
    public long[][][] matrix;
    public int div;
    public int maxNumbers;
   
    public long knapsack(int sum, int indexNumbers, int numConsideredNumbers) {
        if (numConsideredNumbers == maxNumbers) {
            if (sum == 0) {
                return 1;
            }
            return 0;
        }
        else if (indexNumbers < 0) {
            return 0;
        }
       
        if (matrix[sum][indexNumbers][numConsideredNumbers] != -1) {
            return matrix[sum][indexNumbers][numConsideredNumbers];
        }
       
        long use = knapsack(((sum+numbers[indexNumbers]%div)%div+div)%div, indexNumbers-1, numConsideredNumbers+1);
        long notUse = knapsack(sum, indexNumbers-1, numConsideredNumbers);
        matrix[sum][indexNumbers][numConsideredNumbers] = use+notUse;
        return matrix[sum][indexNumbers][numConsideredNumbers];
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int numCase = 0;
       
        int numNumbers = sc.nextInt();
        int numQueries = sc.nextInt();
        while (numNumbers != 0 || numQueries != 0) {
            numbers = new int[numNumbers];
            for (int i = 0; i < numNumbers; i++) {
                numbers[i] = sc.nextInt();
            }
           
            matrix = new long[20][202][12];
            bw.write("SET " + ++numCase + ":\n");
            for (int i = 0; i < numQueries; i++) {
                div = sc.nextInt();
                maxNumbers = sc.nextInt();
                for (int l = 0; l < 20; l++) {
                    for (int j = 0; j < 202; j++) {
                        for (int k = 0; k < 12; k++) {
                            matrix[l][j][k] = -1;
                        }
                    }
                }
                bw.write("QUERY " + (i+1) + ": " + knapsack(0, numNumbers-1, 0)+"\n");
            }
           
            numNumbers = sc.nextInt();
            numQueries = sc.nextInt();
        }
                               
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}