1
Hier ist mein implementierter Code in Java. Die getmax() Funktion gibt den Index des maximalen Elements zurück. Das Problem ist, ich bekomme keinen meiner Testfälle richtig. Ich weiß nicht, welche, aber Online-Richter mir gibt folgende Warnung:Problem mit gebrochenem Rucksack
fehlgeschlagen Fall # 7/13: Falsche Antwort bekam: 66.152,57 erwartet: 66.152,572 (Time verwendet: 0,19/1,50, Speicher verwendet :. 24469504/671088640)
public class FractionalKnapsack {
private static double getOptimalValue(int capacity, int[] values, int[] weights) {
float value = 0;
//write your code here
float[] ratio=new float[values.length];
for(int i=0;i<values.length;i++)
{
ratio[i]=(float)values[i]/(float)weights[i];
}
int max=0;
while(capacity>-1)
{
max=getMax(ratio);
if(capacity==0)
{
return value;
}
if(capacity>0)
{
if(weights[max]>=capacity)
{
value=value+((float)ratio[max]*(float)(capacity));
capacity=0;
}
else if(capacity>weights[max])
{
value=value+(weights[max]*ratio[max]);
capacity=capacity-weights[max];
}
ratio[max]=0;
}
}
return value;
}
private static int getMax(float[] arr)
{
float max=0;
int save=0;
for(int i=0;i<arr.length;i++)
{
if(arr[i]>max)
{
max=arr[i];
save=i;
}
}
return save;
}
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int capacity = scanner.nextInt();
int[] values = new int[n];
int[] weights = new int[n];
for (int i = 0; i < n; i++) {
values[i] = scanner.nextInt();
weights[i] = scanner.nextInt();
}
DecimalFormat df = new DecimalFormat();
df.applyPattern(".0000");
System.out.println(df.format(getOptimalValue(capacity, values, weights)));
}
}
Ihre Antwort ist durch .002 aus, so dass es nur ein einfacher Rundungsfehler oder Formatierung in Ihrem Druck sein muss –
Das ist eine sehr enge Antwort. Nur eine Vermutung, aber haben Sie versucht, Doppel zu verwenden? – IVlad