Find the minmum stamps based on the request.

StampVendingMachine.java

/*
Stamp Vending Machine
It is for dispensing the minimum stamps based on the available stamps in the machine.

How to use:
1. Compile: javac StampVendingMachine.java
2. Run: java StampVendingMachine
3. > 32
output: 2
ctrl + c to terminate
*/

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

interface VendingMachine {
	int min_number_of_stamps(ArrayList<Integer> array, int array_size, int request);
}

public class StampVendingMachine implements VendingMachine{
	public Hashtable<Integer, ArrayList<Integer>> table =
							new Hashtable<Integer, ArrayList<Integer>>();
			// It is for recursive algorithm
			// key: request
			// value: minmum stamps to meet the request
	public ArrayList<Integer> stamps; // all available stamps
	public int size; // size of the stamps

	/*
	wrapper function
	*/
	public int min_number_of_stamps(ArrayList<Integer> array, int array_size, int request) {
		stamps = array;
		size = array_size;
		ArrayList<Integer> rst = min_number_of_stamps(request);
		// System.out.println(rst);
		int index = rst.size() - 1;
		return rst.get(index);
	}

	/*
	It find the minmum # of stammps needed to dispense stamps
	*/
	private ArrayList<Integer> min_number_of_stamps(int request) {
		ArrayList<Integer> choices = new ArrayList<Integer>();
		choices.add(0);

		for (int i = 1; i <= request; i++) {
			int min_choice = get_min_choice(i, choices);
			choices.add(min_choice);
		}

		return choices;
	}

	/*
	Helper function: find out the minmum choice to meet the request based on the
	available stamps
	*/
	private int get_min_choice(int req, ArrayList<Integer> choices) {
		int min_choice = Integer.MAX_VALUE;
		for (int stamp : stamps) {
			if (stamp <= req) {
				// 1 + the minmum choice from previous request
				int choice = 1 + choices.get(req - stamp);
				if (choice < min_choice) {
					min_choice = choice;
				}
			}
		}
		return min_choice;
	}


	/*
	Below is a recursive way but it will stackoverflow when the denomination is
	too large.
	It is a recursive way to find the minmum # of stamps needed to dispense stamps
	*/
	private ArrayList<Integer> rec_min_number_of_stamps(int request) {
		if (table.containsKey(request)) {
			// Reuse the previous request to get the min stamps
			return table.get(request);
		} else if (request > 0) {
			ArrayList<ArrayList<Integer>> choices = new ArrayList<ArrayList<Integer>>();
			ArrayList<Integer> choice = new ArrayList<Integer>();

			for (int i = 0; i < size; i++) {
				if (request >= stamps.get(i)) {
					choice.addAll(min_number_of_stamps(request - stamps.get(i)));
					// new choice = min stamps of previous request + stamp;
					choice.add(stamps.get(i));
					ArrayList<Integer> tmp = new ArrayList<Integer>(choice);
					choices.add(tmp);
					choice.clear();
				}
			}

			// Put the choice of minmum stamps for the request to the table
			table.put(request, get_min_choice(choices));
			return table.get(request);
		}
		ArrayList<Integer> tmp = new ArrayList<Integer>();
		table.put(0, tmp);
		return tmp;
	}

	/*
	Find the minmum element based on the size of the element
	*/
	public ArrayList<Integer> get_min_choice(ArrayList<ArrayList<Integer>> choices) {
		int min = choices.get(0).size();
		int min_index = 0;
		int choice_size = choices.size();

		for (int i = 0; i < choice_size; i++) {
			if (min > choices.get(i).size()) {
				min = choices.get(i).size();
				min_index = i;
			}
		}
		return choices.get(min_index);
	}

	public static void main(String[] args) {
		// Testing
		ArrayList<Integer> ary = new ArrayList<Integer>();
		// int[] test = {1,2,5,9,10,23,40,58,60,75,85,95,100,101,120};
		// int[] test = {1};
		// int[] test = {1,4,5};
		// int[] test = {1,9,13};
		// int[] test = {1,3,5,9,10,12,14,15,25};
		// int[] test = {1,19,190,195,210};
		int[] test = {90,30,24,15,12,10,5,3,2,1};
		for (int i = 0; i < test.length; i++) {
			ary.add(test[i]);
		}
		StampVendingMachine sm = new StampVendingMachine();
		try {
			BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	    	String s;
	    	while ((s = in.readLine()) != null && s.length() != 0) {
	    		int request = Integer.parseInt(s);
				int min = sm.min_number_of_stamps(ary, ary.size(), request);
				System.out.println("Min stamps: " + min);
	    	}
		} catch	(Exception e) {
			System.out.println(e);
		}
	}

}