Beispielcode zur Lösung des Rucksackproblems in Java

In diesem Artikel wird hauptsächlich der Beispielcode zur Lösung von Java-Rucksäcken vorgestellt, der zwei Arten von Rucksäcken umfasst: 01 und vollständige Rucksäcke. Es werden jeweils die Ideen und Umsetzungsmethoden der beiden Rucksäcke beschrieben, die einen gewissen Referenzwert haben.

Das Rucksackproblem bezieht sich hauptsächlich auf einen Rucksack mit einer bestimmten Kapazität und einer Anzahl von Gegenständen mit einem bestimmten Wert und Gewicht. Wie wählt man die Gegenstände aus, die in den Rucksack gesteckt werden sollen, um den Wert der Gegenstände zu maximieren? Es ist in 01-Rucksack und unbegrenzten Rucksack unterteilt. Hier besprechen wir hauptsächlich den 01-Rucksack, was bedeutet, dass jeder Artikel höchstens einen Platz hat. Der Infinite-Rucksack kann in einen 01-Rucksack umgewandelt werden.

Lassen Sie uns zunächst über die Hauptidee des Algorithmus sprechen und ihn mithilfe dynamischer Programmierung lösen. Jedes Mal, wenn der i-te Gegenstand durchlaufen wird, wird anhand von w[i] und v[i] bestimmt, ob der Gegenstand in den Rucksack gesteckt werden muss. Das heißt, für gegebene n Artikel seien v[i] und w[i] der Wert bzw. das Gewicht des i-ten Artikels und C die Kapazität des Rucksacks. Sei v[i][j] der Maximalwert der ersten i Gegenstände, die in einen Rucksack mit der Kapazität j geladen werden können. Dann haben wir folgende Ergebnisse:

(1), v[i][0]=v[0][j]=0;
(2), v[i][ j]=v[i-1][j] Wenn w[i]>j
(3), v[i][j]=max{v[i-1][j],v[i -1][j-w[i]]+v[i]} Wenn j>=w[i]

Okay, unser Algorithmus basiert auf diesen drei Schlussfolgerungsformeln.

1. 01 Rucksack:

1 >

Ausgabe:

public class sf { 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] weight = {3,5,2,6,4}; //物品重量 
    int[] val = {4,4,3,5,3}; //物品价值 
    int m = 12; //背包容量 
    int n = val.length; //物品个数 
    int[][] f = new int[n+1][m+1]; //f[i][j]表示前i个物品能装入容量为j的背包中的最大价值 
    int[][] path = new int[n+1][m+1]; 
    //初始化第一列和第一行 
    for(int i=0;i<f.length;i++){ 
      f[i][0] = 0; 
    } 
    for(int i=0;i<f[0].length;i++){ 
      f[0][i] = 0; 
    } 
    //通过公式迭代计算 
    for(int i=1;i<f.length;i++){ 
      for(int j=1;j<f[0].length;j++){ 
        if(weight[i-1]>j) 
          f[i][j] = f[i-1][j]; 
        else{ 
          if(f[i-1][j]<f[i-1][j-weight[i-1]]+val[i-1]){ 
            f[i][j] = f[i-1][j-weight[i-1]]+val[i-1]; 
            path[i][j] = 1; 
          }else{ 
            f[i][j] = f[i-1][j]; 
          } 
          //f[i][j] = Math.max(f[i-1][j], f[i-1][j-weight[i-1]]+val[i-1]); 
        } 
      } 
    } 
    for(int i=0;i<f.length;i++){ 
      for(int j=0;j<f[0].length;j++){ 
        System.out.print(f[i][j]+" "); 
      } 
      System.out.println(); 
    } 
    int i=f.length-1; 
    int j=f[0].length-1; 
    while(i>0&&j>0){ 
      if(path[i][j] == 1){ 
        System.out.print("第"+i+"个物品装入 "); 
        j -= weight[i-1]; 
      } 
      i--; 
    } 
  } 
}

Die zeitliche und räumliche Komplexität der obigen Methode sind beide O(N). *V) kann die Zeitkomplexität grundsätzlich nicht mehr optimiert werden, wohl aber die Raumkomplexität auf O(V).

0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 4 4 4 4 4 4 4 4 4 4 
0 0 0 4 4 4 4 4 8 8 8 8 8 
0 0 3 4 4 7 7 7 8 8 11 11 11 
0 0 3 4 4 7 7 7 8 9 11 12 12 
0 0 3 4 4 7 7 7 8 10 11 12 12 
第4个物品装入 第3个物品装入 第1个物品装入

Überlegen Sie zunächst, wie Sie die oben erwähnte Grundidee umsetzen. Es muss eine Hauptschleife i=1..N geben und jedes Mal das zweidimensionale Array f[i][0..V ] werden alle Werte berechnet. Wenn also nur ein Array f[0..V] verwendet wird, kann dann garantiert werden, dass f[v] nach dem Ende der i-ten Schleife den von uns definierten Zustand f[i][v] darstellt? f[i][v] wird rekursiv aus den beiden Teilproblemen f[i-1][v] und f[i-1][v-c[i]] abgeleitet. (das heißt, wenn f[v] in der i-ten Hauptschleife verschoben wird), können die Werte von f[i-1][v] und f[i-1][v-c[i]] erhalten werden? Tatsächlich erfordert dies, dass wir f[v] in jeder Hauptschleife in der Reihenfolge v=V..0 pushen, um sicherzustellen, dass f[v-c[i]] den Zustand f speichert, wenn f[v] gedrückt wird [i -1][v-c[i]] Wert.

Der Pseudocode lautet wie folgt:

wobei f[v]=max{f[v],f[v-c[i] ]} Dieser Satz entspricht genau unserer Übertragungsgleichung f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}, denn nun ist f[v-c [ i]] entspricht dem Original f[i-1][v-c[i]]. Wenn die zyklische Reihenfolge von v von der oben genannten umgekehrten Reihenfolge geändert wird, wird sie zu f[i][v]. Dies kann aus f[i][v-c[i]] abgeleitet werden, was mit der Bedeutung nicht übereinstimmt dieser Frage, aber es ist eine andere. Ein wichtiges Rucksackproblem P02 ist die einfachste Lösung, daher ist es sehr wichtig zu lernen, das 01 Rucksackproblem nur mit eindimensionalen Arrays zu lösen.

for i=1..N
  for v=V..0
    f[v]=max{f[v],f[v-c[i]]+w[i]};

Unter den Fragen, die wir gesehen haben, um die optimale Lösung für das Rucksackproblem zu finden, gibt es tatsächlich zwei verschiedene Arten, sie zu stellen. Einige Fragen erfordern die optimale Lösung, wenn der Rucksack genau gefüllt ist, während andere Fragen nicht erfordern, dass der Rucksack gefüllt sein muss. Eine Implementierungsmethode, die diese beiden Fragen unterscheidet, besteht darin, bei der Initialisierung einen Unterschied zu machen.

Wenn es die erste Frage ist, die erfordert, dass der Rucksack genau gefüllt wird, dann werden während der Initialisierung außer f[0] 0, andere f[1..V] auf -∞ gesetzt, Damit kann garantiert werden, dass das endgültige f[N] eine optimale Lösung ist, die den Rucksack gerade noch füllt.

Wenn keine Anforderung besteht, den Rucksack zu füllen, sondern nur der Preis möglichst groß sein soll, sollten bei der Initialisierung alle f[0..V] auf 0 gesetzt werden.

Warum? Dies kann folgendermaßen verstanden werden: Das initialisierte f-Array ist tatsächlich der rechtliche Zustand, in dem keine Gegenstände in den Rucksack gelegt werden können. Wenn eine exakte Befüllung des Rucksacks gefordert wird, darf nur der Rucksack mit einer Kapazität von 0 „exakt gefüllt“ werden, mit nichts mit einem Wert von 0. Für Rucksäcke mit anderen Kapazitäten gibt es keine rechtliche Lösung und sie befinden sich in einem undefinierten Zustand , und ihre Werte sind alle Es sollte -∞ sein. Wenn der Rucksack nicht gefüllt werden muss, gibt es für einen Rucksack mit beliebigem Fassungsvermögen die zulässige Lösung „Nichts packen“. Der Wert dieser Lösung ist 0, daher sind die Anfangszustandswerte alle 0.

2. Eindimensionale Array-Methode (kein Ausfüllen erforderlich)

Ausgabe

public class sf { 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] weight = {3,5,2,6,4}; //物品重量 
    int[] val = {4,4,3,5,3}; //物品价值 
    int m = 12; //背包容量 
    int n = val.length; //物品个数 
    int[] f = new int[m+1]; 
    for(int i=0;i<f.length;i++){   //不必装满则初始化为0 
      f[i] = 0; 
    } 
    for(int i=0;i<n;i++){ 
      for(int j=f.length-1;j>=weight[i];j--){ 
        f[j] = Math.max(f[j], f[j-weight[i]]+val[i]); 
      } 
    } 
    for(int i=0;i<f.length;i++){ 
      System.out.print(f[i]+" "); 
    } 
    System.out.println(); 
    System.out.println("最大价值为"+f[f.length-1]); 
  } 
}

0 0 3 4 4 7 7 7 8 10 11 12 12 
最大价值为12

3. Eindimensionale Array-Methode (muss ausgefüllt werden)

Ausgabe

public class sf { 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] weight = {3,5,2,6,4}; //物品重量 
    int[] val = {4,4,3,5,3}; //物品价值 
    int m = 12; //背包容量 
    int n = val.length; //物品个数 
    int[] f = new int[m+1]; 
    for(int i=1;i<f.length;i++){   //必装满则f[0]=0,f[1...m]都初始化为无穷小 
      f[i] = Integer.MIN_VALUE; 
    } 
    for(int i=0;i<n;i++){ 
      for(int j=f.length-1;j>=weight[i];j--){ 
        f[j] = Math.max(f[j], f[j-weight[i]]+val[i]); 
      } 
    } 
    for(int i=0;i<f.length;i++){ 
      System.out.print(f[i]+" "); 
    } 
    System.out.println(); 
    System.out.println("最大价值为"+f[f.length-1]); 
  } 
}

0 -2147483648 3 4 3 7 6 7 8 10 11 12 11 
最大价值为11

2. Kompletter Rucksack
Es gibt N Arten von Gegenstände und eine Kapazität von Vs Rucksack haben von jedem Gegenstand unbegrenzte Stücke zur Verfügung. Die Kosten des i-ten Artikels sind c[i] und der Wert ist w[i]. Finden Sie heraus, welche Gegenstände in einen Rucksack gepackt werden können, sodass die Gesamtkosten dieser Gegenstände das Fassungsvermögen des Rucksacks nicht überschreiten und die Summe ihrer Werte maximal ist.

Aber wir haben einen besseren O(VN)-Algorithmus.

O(VN)-Algorithmus
Dieser Algorithmus verwendet ein eindimensionales Array, schauen wir uns den Pseudocode an Zuerst:

Sie werden feststellen, dass sich dieser Pseudocode nur in der Schleifenreihenfolge von v vom Pseudocode von P01 unterscheidet.

for i=1..N
  for v=0..V
    f[v]=max{f[v],f[v-cost]+weight}

Ausgabe

public class test{ 
   public static void main(String[] args){ 
      int[] weight = {3,4,6,2,5}; 
      int[] val = {6,8,7,5,9}; 
      int maxw = 10; 
      int[] f = new int[maxw+1]; 
      for(int i=0;i<f.length;i++){ 
        f[i] = 0; 
      } 
      for(int i=0;i<val.length;i++){ 
        for(int j=weight[i];j<f.length;j++){ 
          f[j] = Math.max(f[j], f[j-weight[i]]+val[i]); 
        } 
      } 
      System.out.println(f[maxw]); 
   } 
  }

25

总结

Das obige ist der detaillierte Inhalt vonBeispielcode zur Lösung des Rucksackproblems in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!