[JAVA] Résoudre le problème du sac à dos avec une planification dynamique

[Algorithmes et structures de données pour les programmeurs Java](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) est utilisé comme référence. Le code source est répertorié sur GitHub.

import java.util.*;

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

  //Un objet qui représente un problème de sac à dos
  public Knapsack(int[] size, int[] value) {
    if (size.length != value.length) {
      throw new IllegalArgumentException("'size'Quand'value'Le nombre d'éléments ne correspond pas");
    }

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

  
  //Mettez diverses choses dans un sac à dos de taille 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("La taille du sac à dos%d%n", m);

    //Mettez les articles un par un et recherchez la valeur maximale de bas en haut
    for (int i = 0; i < N; i++) {

      //Mettez l'article i un par un
      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("des biens%d (valeur%d)Des trucs%n", choice[i], value[choice[i]]);
    }
    System.out.printf("Valeur totale= %d%n", total[m]);
  }


  public static void abort(String message) {
    System.err.printf("Comment commencer:java taille du sac à dos%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("Le nombre de paramètres est différent.");
    }
    try {
      size = Integer.parseInt(args[0]);
    } catch (NumberFormatException e) {
      abort("Spécifiez un entier positif pour la taille");
    }
    if (size <= 0) {
      abort("Spécifiez un entier positif pour la taille");
    }

    knapsack.solve(size);
  }
}