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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.