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;
}
}