[JAVA] Lösung des Rucksackproblems mit dynamischer Planung

[Algorithmen und Datenstrukturen für Java-Programmierer](https://www.amazon.co.jp/Java%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9% E3% 83% 9E% E3% 81% AE% E3% 81% 9F% E3% 82% 81% E3% 81% AE% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0% E3% 81% A8% E3% 83% 87% E3% 83% BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0-% E8% BF% 91% E8% 97% A4-% E5% 98% 89% E9% 9B% AA / dp / 4797326603) wird als Referenz verwendet. Der Quellcode ist auf [GitHub] aufgeführt (https://github.com/be-kan/knapsack_with_dynamic_programming).

import java.util.*;

public class Knapsack {
  int[] size;
  int[] value;
  int N;

  //Ein Objekt, das ein Rucksackproblem darstellt
  public Knapsack(int[] size, int[] value) {
    if (size.length != value.length) {
      throw new IllegalArgumentException("'size'Wann'value'Die Anzahl der Elemente stimmt nicht überein");
    }

    this.N = size.length;
    this.size = (int[])size.clone();
    this.value = (int[])value.clone();
  }

  
  //Legen Sie verschiedene Dinge in einen Rucksack der Größe m
  public void solve(int m) {
    int[] total = new int[m+1];
    int[] choice = new int[m+1];
    Arrays.fill(choice, -1);
    int repackTotal;
    System.out.printf("Die Größe des Rucksacks%d%n", m);

    //Legen Sie die Gegenstände einzeln ein und suchen Sie den maximalen Wert von unten nach oben
    for (int i = 0; i < N; i++) {

      //Setze den Gegenstand nacheinander ein
      for (int j = size[i]; j <= m; j++) {
        repackTotal = total[j - size[i]] + value[i];
        if (repackTotal > total[j]) {
          total[j] = repackTotal;
          choice[j] = i;
        }
      }

      System.out.printf("i = %d%n", i);
      System.out.printf("total = ");
      for (int j = 0; j <= m; j++) {
        System.out.printf("%4d", total[j]);
      }
      System.out.printf("%nchoice = ");
      for (int j = 0; j <= m; j++) {
        System.out.printf("%4d", choice[j]);
      }
      System.out.printf("\n");
    }

    for (int i = m; choice[i] >= 0; i -= size[choice[i]]) {
      System.out.printf("Waren%d (Wert%d)Sachen%n", choice[i], value[choice[i]]);
    }
    System.out.printf("Gesamtwert= %d%n", total[m]);
  }


  public static void abort(String message) {
    System.err.printf("Wie man anfängt:Java-Rucksackgröße%n");
    System.err.printf("%s%n", message);
    System.exit(1);
  }


  public static void main(String args[]) {
    Knapsack knapsack = new Knapsack(
      new int[] {2, 3, 5, 7, 9},
      new int[] {2, 4, 7, 11, 14}
    );

    int size = 0;
    if (args.length != 1) {
      abort("Die Anzahl der Parameter ist unterschiedlich.");
    }
    try {
      size = Integer.parseInt(args[0]);
    } catch (NumberFormatException e) {
      abort("Geben Sie eine positive Ganzzahl für die Größe an");
    }
    if (size <= 0) {
      abort("Geben Sie eine positive Ganzzahl für die Größe an");
    }

    knapsack.solve(size);
  }
}