(UVA) CD - Solution

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

The solution below is using backtracking. The approach used is to consider using a track or not in order to obtain the maximum sum of tracks.



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

class Main {
    public static int lenghtTape;
    public static int numTracks;
    public static int[] tracks;
    public static ArrayList<Integer> chosenTracks;
    public static ArrayList<Integer> previousChoices;
    public static int max;
   
    public static void rec(int currTrack, int sum) {
        if (currTrack >= numTracks) {
            if (sum >= max && sum <= lenghtTape) {
                max = sum;
                chosenTracks = (ArrayList<Integer>) previousChoices.clone();
            }
            return;
        }
        for (int i = 0; i < 2; i++) {
            if (i == 1) {
                previousChoices.add(tracks[currTrack]);
            }
            rec(currTrack+1, sum+tracks[currTrack]*i);
            if (i == 1) {
                previousChoices.remove((Object)tracks[currTrack]);
            }
        }
    }
   
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        while (sc.hasNext()) {
            String line = sc.nextLine();
            String[] s = line.split("\\s");
           
            lenghtTape = Integer.parseInt(s[0]);
            numTracks = Integer.parseInt(s[1]);
            tracks = new int[numTracks];
            for (int i = 0; i < numTracks; i++) {
                tracks[i] = Integer.parseInt(s[2+i]);
            }
           
            max = 0;
            previousChoices = new ArrayList<>();
            chosenTracks = new ArrayList<>();
            rec(0, 0);
           
            for (int i = 0; i < chosenTracks.size(); i++) {
                System.out.print(chosenTracks.get(i) + " ");
            }
            System.out.println("sum:"+ max);
        }
                               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}