UVA – 165 – Stamps   Leave a comment


Simple backtracking + dp to find n for a given coin domination

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Stamps {
	static int optimal;
	static Stack<Integer> best;

	public static int func(Stack<Integer> s, int h) {
		int max = s.peek() * h + 1;
		int[] count = new int[max];
		Arrays.fill(count, Integer.MAX_VALUE);
		count[0] = 0;
		for (int i = 0; i < max; i++) {
			if (count[i] > h) {
				return i - 1;
			}
			for (int j : s)
				if (i + j < max)
					count[i + j] = Math.min(count[i + j], 1 + count[i]);
		}
		return max - 1;
	}

	public static void n(int h, int k, Stack<Integer> s) {
		if (k == 0) {
			int current = func(s, h);
			if (current > optimal) {
				optimal = current;
				best = (Stack<Integer>) s.clone();
			}

		} else {
			int current = func(s, h);
			for (int j = s.peek() + 1; j <= current + 1; j++) {
				s.push(j);
				n(h, k - 1, s);
				s.pop();
			}
		}
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		while (true) {
			int h = in.nextInt(), k = in.nextInt();
			if (h == 0 && k == 0)
				break;
			Stack<Integer> S = new Stack<Integer>();
			S.push(1);
			optimal = 1;
			n(h, k - 1, S);
			for (int i : best)
				System.out.printf("%3d", i);
			System.out.printf(" ->%3d\n", optimal);

		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

Advertisements

Posted June 20, 2012 by epicrado in Recursive Backtracking

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: