[ create a new paste ] login | about

Link: http://codepad.org/cLkK1ov5    [ raw code | output | fork ]

C, pasted on Mar 24:
	public subset()
	{
		Scanner keyin = new Scanner(System.in);
		getset(keyin);
		System.out.println("Enter value for M:");
		M = keyin.nextInt();
		store = new int[N+1];
		for (int i=1; i<=N; i++) store[i]=0; // For branch and bound algorithms,
		// the store and size arrays are the same size.

		
		// The code below uses dynamic programming to obtain a pseudo-polynomial
		// solution to the subset sum problem.   Note that the time for
		// this algo. can easily be predicted: Theta(NM).  This seems polynomial, but
		// recall that M is the sum of a subset, whose items can be arbitrarily large.
		// Thus, the algorithm can in fact be slower than the branch and bound algorithm
		// in some cases.  Consider file subset4.dat and you can see where the dynamic
		// programming algorithm falters.  Also remember that the dynamic programming
		// algorithm requires Theta(M) memory, and this certainly can be a problem for
		// large M as well.
		System.out.println("John's Dynamic Programming Algo: ");
		states = 0;
		store = new int[M+1];	// For dynamic programming algorithm, the store array
								// needs to be size M+1
		for (int i = 1; i<=M; i++)
			store[i]=0;
		store[0] = -1;   // set store 0 to dummy non-zero value
		for (int j = 1; j <= N; j++)	// each time try to solve the problem
										// considering an additional item
		{
			for (int i = 1; i <= M; i++)
			{
				states++;
				if ((i >= size[j]) && (store[i - size[j]] != 0) && (j != store[i - size[j]])
					&& (store[i] == 0))

					// add item to solution for a given M only if
					// Condition 1) M is at least as big as the item considered
					// Condition 2) A solution has been found for M - size of the
					//              current item
					// Condition 3) The same item is not already used in the previous
					//              part of the solution
					// Condition 4) No solution has yet been found for the current M
				{
					//System.out.println("store[" + i + "]= " + j);
					store[i] = j;
					states++;
				}
			}
		}
		if (store[M] > 0)	// Solution found
		{
			for (int i = M; i > 0; i = i - size[store[i]])
				System.out.print(size[store[i]] + " ");
			System.out.println(" in " + states + " statements ");
		}
		else
			System.out.println("No solution found after " +	states + " statements ");
	}

	public static void main(String [] args)
	{
		new subset();
	}


Output:
1
2
Line 1: error: expected '=', ',', ';', 'asm' or '__attribute__' before 'subset'
Line 61: error: expected '=', ',', ';', 'asm' or '__attribute__' before 'static'


Create a new paste based on this one


Comments: