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...)


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]) * 

		//the most preferred spice is now calculated:
		for(int i = 1; i < numOfPiles; i++){
			double comparisonValue = Double.parseDouble(inputStore[3*i+2])*
			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 don't know how to keep track of the other spices' order of preference.

Sounds like a sort should give you the spices in order of preference.
How are you storing the data about your spices? You should create a Spice class that stores the info for each spice.
If you store the Spice objects you create in a list of some kind, you can sort the list in preference order.

This article has been dead for over six months. Start a new discussion instead.