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

public class ProgramKnapsackSimple {

	private static Vector<Integer> generate(int length) {
		// Generates a vector of length random integers 
		// all elements having values in [1..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(IKnapsackSimple solver,
			Vector<Integer> weights, int last, int k, boolean isDemo) {
	
		boolean solution;

		if (isDemo) {
			System.out.println("The weights are:");
			for (int i = 0; i <= last; i++)
				System.out.print(weights.get(i) + " ");
			System.out.println();
			System.out
					.println("The sum of the selected weights must be K=" + k);
		}

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

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

	}

	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

		// uses an implementation of the simple knapsack
		// replace with your optimized implementation !
		IKnapsackSimple solver1 = new KnapsackSimple_Recursive();

		System.out.println("The Simple Knapsack Problem (only boolean answer)");

		/* A small demo case */
		System.out.println("I will run a small demo case.");
		System.out.println("Press ENTER to continue with it ...");
		waitForEnter();
		System.out.println("Wait, I am working ...");
		n = 8;
		k = n * 2;
		weights = generate(n);
		doAnalysis(solver1, 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(solver1, 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();

		n = 10000;
		k = n * 5;
		weights = generate(n);
		// the simple recursive solver will not work here !
		// the dynamic programming version using the big table will not work here !
		doAnalysis(solver1, weights, n - 1, k, false);

	}

}