private int knapsack(int n, int capacity, int w[], int v[])
	{
		// dynamic programming
		if (vKnapsack[capacity] != Integer.MIN_VALUE)
			return vKnapsack[capacity];

		// Find the optimal value that can carried in a knapsack of given
		// capacity
		// The optimal value that can be carried is the maximum of the optimal
		// subproblem solutions.
		// Each subproblem here represents a choice of including one of the
		// items in the knapsack and optimally packing into the rest of the
		// knapsack
		int max = 0;
		for (int i = 0; i < n; i++)
		{
			// remove this to get a solution for the unbounded problem
			if (inKnapsack[i])
				continue;
		
			// Is there space(non-negative) in the knapsack to add item i
			int space = capacity - w[i];
			if (space < 0)
				continue;

			// Result of optimally packing in the remaining space
			int t = knapsack(n, space, w, v);

			// optimal solution is the max of all subproblems.
			if (v[i] + t > max)
			{
				max = v[i] + t;
				contentsKnapsack[capacity] = w[i] + " "
						+ contentsKnapsack[space];
				inKnapsack[i] = true;
			}

		}

		vKnapsack[capacity] = max;
		return vKnapsack[capacity];
	}