import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Random;
import java.util.Vector;

public class ProgramKnapsackComplete {

	/**
	 * Generates a vector of random integers having values in [1..length]
	 * 
	 * @param length
	 *            the size of the vector
	 * @return the generated vector
	 */
	private static Vector<Integer> generate(int length) {
		Vector<Integer> s = new Vector<Integer>(length);
		Random r = new Random();
		for (int i = 0; i < length; i++)
			s.add(i, 1 + r.nextInt(length));
		return s;
	}

	private static void doAnalysis(IKnapsackComplete solver,
			Vector<Integer> weights, int last, int k, boolean isDemo) {

		if (isDemo) {
			System.out.println("The " + (last + 1)
					+ " candidates have following weights:");
			for (int i = 0; i < weights.size(); i++)
				System.out.print(weights.get(i) + " ");
			System.out.println();

			System.out.println("The total weight must be k=" + k);
		}

		ArrayList<Integer> solution = null;

		long startTime = System.nanoTime();
		solution = solver.getSolution(weights, last, k);
		long endTime = System.nanoTime();
		System.out.println("duration=" + (endTime - startTime) / 1000000+" milisec");

		if (solution == null)
			System.out.println("No solution");
		else {
			System.out.println("Found solution ");

			if (isDemo) {
				System.out.println("Solution contains following weights: ");
				for (int i = 0; i < solution.size(); i++)
					System.out.print(solution.get(i) + " ");
				System.out.println();
			}

			int w = 0;
			for (int i = 0; i < solution.size(); i++)
				w = w + solution.get(i);
			if (w != k) // check that the sum of the weights is indeed k
				System.out.println("ERROR !");
		}
	}

	private static void waitForEnter() {
		DataInputStream input = new DataInputStream(System.in);
		try {
			input.readLine();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	public static void main(String[] args) {

		int n; // number of items
		Vector<Integer> weights = null; // weights of items
		int k; // total weight

		System.out
				.println("The Complete Knapsack Problem (answer contains list of selected items)");

		// use an implementation of the complete knapsack problem

		// here the current solver implements the recursive method
		// implement better solvers using dynamic programming techniques !
		IKnapsackComplete solver = new KnapsackComplete_Recursive();

		/* A small demo case */
		System.out.println("I will run a small demo case.");
		System.out.println("Press ENTER to continue with it ...");
		waitForEnter();

		n = 8;
		k = n * 2;
		weights = generate(n); // generate random n weights
		doAnalysis(solver, weights, n - 1, k, true);

		/* A medium size case */
		System.out.println("\nI will run a medium size case.");
		System.out.println("Press ENTER to continue with it ...");
		waitForEnter();
		System.out.println("Wait, I am working ...");
		n = 1000;
		k = n * 5;
		weights = generate(n);
		doAnalysis(solver, weights, n - 1, k, false);

		/* A large size case */
		System.out.println("\nI will try to run a large size case.");
		System.out
				.println("If it is not working, implement a better Knapsack solver !!!");
		System.out.println("Press ENTER if you want to try ...");
		waitForEnter();
		System.out.println("Wait, I am working ...");
		n = 10000;
		k = n * 3;
		weights = generate(n);
		// this will not work !
		doAnalysis(solver, weights, n - 1, k, false);
	}

}