Fractional Knapsack Java-Implementierung

Question

So bekomme ich die ganze Idee des gebrochenen Rucksackproblems, das ist, Ihren Behälter mit Bruchmengen der gegebenen Einzelteile, die Sie haben, optimal zu füllen.

Allerdings bin ich verwirrt, wie ich diesen Algorithmus in eine Java-Funktion implementieren kann? Ich muss es für meinen Coursera Kurs lösen. Wenn jemand erklären kann, wie man diese Funktion schreibt, würde ich es sehr schätzen. Dies ist die Frageaufforderung:

Aufgabe. Das Ziel dieses Codeproblems ist es, einen Algorithmus für das> Fractional-Rucksack-Problem zu implementieren. Eingabeformat. Die erste Zeile der Eingabe enthält die Anzahl n der Items> und die Kapazität W eines Rucksacks. Die nächsten n Zeilen definieren die Werte und Gewichte der Elemente. Die i-te> Zeile enthält Ganzzahlen vi und wi - den Wert und das Gewicht des i-ten Elements. Einschränkungen. 1 ≤ n ≤ 103

Das ist, was ich bisher haben (dies umfasst Starter Code, aus dem der Kurs mir zur Verfügung gestellt)

`

public class FractionalKnapsack { 
    private static double getOptimalValue(int capacity, int[] values, int[] weights) { 
     //filling array vallues with 0 
     Arrays.fill(values,0); 
     //total value is 0 
     double value = 0; 

     for(int i=0; i<values.length; i++){ 
      if(W==0){ 
       return 
      } 
     } 
     //write your code here 
     //fit first the item with the maximal value per unit 

     //while knapsack is not full 
     //choose item with maxmimum v/wi 
     //if item fits into knapsack, take all of it 
     //else take so much to fill knapsack to end 
     //return total value and amounts taken 

     return value; 
    } 

    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(); 
     }` 

Answer 1

Versuchen Sie, sich mit folgenden Schritten zu codieren :

1.Nehmen Sie ein Doppel-Array mit Verhältnis von Wert zu Gewicht.

2.Sortieren Sie das Verhältnis-Array zusammen mit dem Gewichts-Array.

3.Produkt von Gewicht und Verhältnis eins nach dem anderen nehmen, bis der Knapsack gefüllt ist.

Answer 2

Fractional Knapsack bedeutet, dass Sie Greedy-Algorithmus verwenden können. Sie sollten den Artikel mit dem höchsten value/weight Ratio füllen. Sortieren Sie alle Ihre Artikel in absteigender Reihenfolge des oben genannten Verhältnisses und beginnen Sie, den Rucksack mit den einzelnen Artikeln zu füllen, bis der Rucksack voll ist.

Für den letzten Artikel, den Sie in einen Rucksack legen, der entweder voll oder teilweise sein kann, hängt von dem Platz ab, der für den letzten Gegenstand im Rucksack übrig ist.