(UVA) Dividing coins - Solution

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

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[][] matrix;
    public int[] coins;
    public int division;

    public int knapsack(int volume, int index) {
        if (volume == 0) {
            return 2;
        }
        else if (volume < 0 || index < 0) {
            return 1;
        }
       
        if (matrix[volume][index] != 0) {
            return matrix[volume][index];
        }
       
        int use = knapsack(volume-coins[index], index-1);
        int notUse = knapsack(volume, index-1);
        matrix[volume][index] = Math.max(use, notUse);
        return matrix[volume][index];
    }
   
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;     
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            }
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp;     
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numTests = reader(br);
        for (int i = 0; i < numTests; i++) {
            int totalCoins = 0;
            int numCoins = reader(br);
            coins = new int[numCoins];
            if (numCoins == 0) {
                bw.write("0\n");
                continue;
            }
           
            for (int j = 0; j < numCoins; j++) {
                coins[j] = reader(br);
                totalCoins += coins[j];
            }
           
            int halfCoins = totalCoins/2;
            int tmp = halfCoins;
            int possible = 1;
            while (possible != 2 && tmp >= 0) {
                matrix = new int[tmp+1][numCoins];
                possible = knapsack(tmp, numCoins-1);
                tmp -= 1;
            }
           
            int firstDivision = tmp+1;
            int secondDivision = totalCoins-firstDivision;
            int result = Math.abs(secondDivision-firstDivision);
            bw.write(result+"\n");
        }
               
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}