(UVA) Luggage - Solution

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

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[] weights;
    public int[][] matrix;
   
    public int knapsack(int volume, int indexLuggage) {
        if (volume == 0) {
            return 2;
        }
        else if (volume < 0 || indexLuggage < 0) {
            return 1;
        }
       
        if (matrix[volume][indexLuggage] != 0) {
            return matrix[volume][indexLuggage];
        }
       
        int use = knapsack(volume-weights[indexLuggage], indexLuggage-1);
        int notUse = knapsack(volume, indexLuggage-1);
        matrix[volume][indexLuggage] = Math.max(use, notUse);
        return matrix[volume][indexLuggage];
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line = br.readLine();
        int numTests = Integer.parseInt(line);
        for (int i = 0; i < numTests; i++) {
            line = br.readLine();
            String[] s = line.split(" ");
            weights = new int[s.length];
            int totalWeight = 0;
            for (int j = 0; j < s.length; j++) {
                weights[j] = Integer.parseInt(s[j]);
                totalWeight += weights[j];
            }
           
            int possible = 0;
            if (totalWeight%2 == 0) {
                int volume = totalWeight/2;
                matrix = new int[volume+1][weights.length];
                possible = knapsack(volume, weights.length-1);
            }
           
            if (possible == 2) {
                bw.write("YES\n");
            }
            else {
                bw.write("NO\n");
            }
        }
       
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}