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:
|
|
Line 1: error: expected '=', ',', ';', 'asm' or '__attribute__' before 'subset'
Line 61: error: expected '=', ',', ';', 'asm' or '__attribute__' before 'static'
|
|