KNAPSACKish problem! PLEASE HELP fast!! Nearly done...

Hi, could someone give me some idea of how I can be more EFFICIENT.

Basically, it is some kind of a Knapsack problem. But the number of items can be in the 100000s, and my solution caters to only around 5, I think.

-------
The story / circumstance:
A thief has found many piles of spices. These spices have different volumes (in m^3), values per gram), and densities (in grams/cm^3). He's got a bag, which has a total volume limit (in m^3). His goal? Leave in one trip, with the most profitable bag of spice.

-------
My approach to the problem so far:
The input to this problem is through stdin (standard input on a command prompt). My approach to collecting this information is by writing a single long string with the input.

Then, I pick out specific parts of the string to get its specific values to perform calculations.

------
What I can do so far:
I can read the input for the problem.
I can get the values from my string, in order to perform calculations and comparisons, and so
I can determine the most preferred/lucrative spice

------
Problem / What I can't do / STUCK!!!
While I can determine the most lucrative spice... I don't know how to keep track of the other spices' order of preference.

(Best spice? I got it, but have space remaining in my bag. Next preferred spice? err... got to perform the whole algorithm again! Third preferred spice? Millionth preferred spice...)

Code:



public class HELPME{

	

	public static String[] inputStore;

	

	public static void main(String[] args) throws IOException{

		

		String input = "";

		int numOfCases = 0;	

		

	        //Getting input:

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		

		String line = null;

		while ((line = in.readLine()) != null && (line.length() != 0)) {	

			input += line + " ";	

			

			

		}	//Now, have completed getting all input.

		


		inputStore = input.split(" ");	//split up the String input, and put into array.


		int readingIndexOfInputStore = 0;

	

		while(numOfCases != 0){

			//solution is the answer to the problem. 

			double solution = calculationForCase(readingIndexOfInputStore);

						

			//Displays the solution.

			System.out.println("Maximum loot value = " + solution);

		}

	}


	

	private static double calculationForCase(int index) {

		//Calculates the solution, and returns the solution, by reading the array inputStore from the 'index' position. 

		

		double maximumSackVolume = Double.parseDouble(inputStore[index+1]);

				

		int numOfPiles = Integer.parseInt(inputStore[index]);	//numOfPiles = number of piles of different spices.

		

		double[]powderPreferences = new double[numOfPiles];


		//some spices' value is calculated.

		double highestValue = Double.parseDouble(inputStore[index+2]) * 

								Double.parseDouble(inputStore[index+3])*	

								Double.parseDouble(inputStore[index+4]);


		//the most preferred spice is now calculated:

		for(int i = 1; i < numOfPiles; i++){

			

			double comparisonValue = Double.parseDouble(inputStore[3*i+2])*

										Double.parseDouble(inputStore[3*i+3])*

										Double.parseDouble(inputStore[3*i+4]);

			

			System.out.println("HighestValue = " + highestValue);

			System.out.println("ComparisonValue = " + comparisonValue);

			

			

			if (highestValue < comparisonValue){	// the highest value becomes the comparison value, for future references. 

				//highestValue is the most preferrred spice.

				highestValue = comparisonValue;			

			}

		}

		//Put in this highestValue spice in the bag 

		//Now, put in the 2nd-most valuable spice in the bag... but which one is that? 

		//            This whole process must start again to find the second most valuable spice! 

		//                   There must be a more efficient way! BUT WHAT IS IT???? 

		//Please help!

			

		

		double calculation = 234523452345235423452.234523545 somethin gsomething something;

		return calculation;


	} 

		

}

I'm not going to rethink what you've already written there, but i'll give you my idea.

1) Create a class named Spice which holds information for spices and implements Comparable<Spice> interface.
2) Create a method inside the Spice class, which calculates the actual value for a cm^3 of spice, based on value and density (value * density). <- the bigger, the more profitable the spice is.
3) Implement the Comparable<Spice> interface's compareTo(Spice other) method, which should compare Spice based on the value we calculated in the second point.
4) In your main method, create all the Spice objects needed, and put them in an ArrayList<Spice>.
5) Sort the Spices, using Collections.sort(theArrayList).
6) Start iterating over the sorted ArrayList<Spice> and collect the first n spices until the bag is filled(The total volume exceeds the knapsack's volume). The last of the collected spice is probably needed to split somehow, because it won't fit as a whole.
You can collect them by inserting them into another ArrayList<Spice>, which is your knapsack.