(UVA) SuperSale - Solution

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

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 Obj[] objects;
   
    public int knapsack(int volume, int index) {
        if (volume < 0) {
            return -1000000000;
        }
        if (index < 0) {
            return 0;
        }
       
        if (matrix[volume][index] != -1) {
            return matrix[volume][index];
        }
       
        int use = knapsack(volume-objects[index].weight, index-1)+objects[index].price;
        int notUse = knapsack(volume, index-1);
        matrix[volume][index] = Math.max(use, notUse);
        return matrix[volume][index];
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            int numObjects = sc.nextInt();
            objects = new Obj[numObjects];
            for (int j = 0; j < numObjects; j++) {
                int price = sc.nextInt();
                int weight = sc.nextInt();
                objects[j] = new Obj(price, weight);
            }
           
            matrix = new int[31][1001];
            for (int j = 0; j < 31; j++) {
                for (int k = 0; k < 1001; k++) {
                    matrix[j][k] = -1;
                }
            }
           
            int sumPurchase = 0;
            int numPeople = sc.nextInt();
            for (int j = 0; j < numPeople; j++) {
                int volume = sc.nextInt();
                int price = knapsack(volume, numObjects-1);
                sumPurchase += price;           
            }

            bw.write(sumPurchase+"\n");
        }
               
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Obj {
    int price;
    int weight;
   
    public Obj(int p, int w) {
        price = p;
        weight = w;
    }
}