(SPOJ) 18550 - Troco - Solução

Solução utilizando o "problema da mochila".
É possível ver como isso funciona através do link: http://pt.wikipedia.org/wiki/Problema_da_mochila

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

class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main processando = new Main();
        processando.processa();
       
        System.exit(0);
    }
   
    static int leitor(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;
    
    }

    boolean funcao (int valorAtual, int[] moedas, int qteMoedas, int valorCompra, int posicao, boolean[][] tabelaVerificadora) {
        if (valorAtual == valorCompra) {
            return true;
        }
        if (posicao == qteMoedas) {
            return false;
        }
        if (valorAtual > valorCompra) {
            return false;
        }
       
        if (tabelaVerificadora[valorAtual][posicao] == true) {
            return false;
        }
        else { // tabelaVerificadora[valorAtual][posicao] == 0
            tabelaVerificadora[valorAtual][posicao] = true;
       
            if (funcao(valorAtual, moedas, qteMoedas, valorCompra, posicao+1, tabelaVerificadora) == true) {
                return true;
            }
            if (funcao(valorAtual + moedas[posicao], moedas, qteMoedas, valorCompra, posicao+1, tabelaVerificadora) == true) {
                return true;
            }
        }
       
        return false;
    }
   
    void processa() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int valorCompra = leitor(br);
        int qteMoedas = leitor(br);
       
        int[] moedas = new int[qteMoedas];
        for (int i = 0; i < qteMoedas; i++) {
            moedas[i] = leitor(br);
        }
       
        boolean[][] tabelaVerificadora = new boolean[valorCompra][qteMoedas];
        boolean encontrouResposta = funcao(0, moedas, qteMoedas, valorCompra, 0, tabelaVerificadora);
               
        if (encontrouResposta) {
            bw.write("S\n");
        }
        else {
            bw.write("N\n");
        }
       
        bw.flush();
        bw.close();           
        return;
    }
}