Java: entiers de traitement par lots

Je me demandais quel était le meilleur moyen de regrouper un ensemble de nombres en termes de temps de traitement. Prendre les articles: 9, 18, 7, 8, 4, 9, 11, 15, 3, 8, (l’article 1 a un temps de traitement de 9, l’article 2 a un temps de traitement de 18, etc.)

Si la limite de temps de traitement par lots est définie à 20, un regroupement possible des éléments en lots serait: {1, 3, 5} {2} {4, 6} {8, 9} {7, 10} ( le groupe 1 est 9 + 7 + 4 = 20), etc. 5 lots d’articles ont donc été créés et le contenu est <= 20.

Idéalement, je souhaite les classer dans le moins de groupes possible. Le cas ci-dessus est un minimum de 5 groupes avec une limite de contenu de 20 …

Merci

Si le délai de traitement par lot est défini sur 20, …

Je suppose donc qu’il n’ya pas d’élément supérieur au délai de traitement par lots . Voici mon approche:

  • Commencez par sortinger les articles. Ensuite, obtenez 2 pointeurs pour la liste, l’un est à l’indice 0 ( pointeur de gauche ) et l’autre au dernier index ( pointeur de droite ).
  • Prenez l’élément de right-pointeur et ajoutez-le à une sous-liste. Prenez l’élément du pointeur de gauche et ajoutez-le à la même sous-liste. Si la sum des éléments de la sous-liste est inférieure à la limite, mettez à jour le pointeur gauche (définissez-le sur l’élément suivant) et essayez de l’append. Continuez ce processus jusqu’à ce qu’une sous-liste soit remplie.
  • Puis commencez à remplir la prochaine sous-liste. Consumz tous les éléments pour construire des sous-listes.

Implémentation en Java:

 int[] input = { 9, 18, 7, 8, 4, 9, 11, 15, 3, 8 }; // Input items. Arrays.sort(input); // Sort the items. int left = 0, right = input.length - 1; // Left and right pointers. int remainder = 0, limit = 20; // list of groups. ArrayList> list = new ArrayList>(); while (right >= left) { ArrayList subList = new ArrayList(); list.add(subList); // Add the current maximum element. subList.add(input[right]); if (right == left) break; remainder = limit - input[right]; right--; // Add small elements until limit is reached. while (remainder > input[left]) { subList.add(input[left]); remainder = remainder - input[left]; left++; } remainder = 0; // Reset the remainder. } 

Imprimer les groupes:

 for (ArrayList subList : list) { for (int i : subList) System.out.print(i + " "); System.out.println(); } 

Sortie: (Chaque ligne désigne un groupe de nombres)

 18 15 3 11 4 9 7 9 8 8 
  1. Prenez le plus grand de l’ensemble IN et insérez un nouvel ensemble S. (élément 2, valeur 18)
  2. Essayez de trouver le plus gros élément avec une valeur <= (20 - 18): aucune, ajoutez S à une liste de jeux.
  3. si IN n’est pas vide GOTO 1

Itérations:

  IN: 9, 18, 7, 8, 4, 9, 11, 15, 3, 8 S1 (18) : 2:18 IN: 9, _, 7, 8, 4, 9, 11, 15, 3, 8 S2 (19) : 8:15, 5:4 IN: 9, _, 7, 8, _, 9, 11, _, 3, 8 S3 (20) : 7:11, 1:9 IN: _, _, 7, 8, _, 9, _, _, 3, 8 S4 (20) : 6: 9, 4:8, 0:3 IN: _, _, 7, _, _, _, _, _, _, 8 S5 (15) : 10: 8, 3:7 IN: _, _, _, _, _, _, _, _, _, _ 

Le code :

 public class Knapsack { public static void knapsack( int capacity, int[] values, List< int[] > indices ) { int[] in = Arrays.copyOf( values, values.length ); List< Integer > workspace = new LinkedList<>(); int wCapacity = capacity; boolean inProgress = true; while( inProgress ) { int greatestValue = -1; int greatestIndex = -1; for( int i = 0; i < in.length; ++i ) { int value = in[i]; if( value > Integer.MIN_VALUE && greatestValue < value && value <= wCapacity ) { greatestValue = value; greatestIndex = i; } } if( greatestIndex >= 0 ) { workspace.add( greatestIndex ); in[greatestIndex] = Integer.MIN_VALUE; wCapacity -= greatestValue; } else if( workspace.isEmpty()) { inProgress = false; } else { int[] ws = new int[workspace.size()]; for( int i = 0; i < workspace.size(); ++i ) { ws[i] = workspace.get(i).intValue(); } indices.add( ws ); workspace = new LinkedList<>(); wCapacity = capacity; } } } static void print( int[] values, List< int[] > indices ) { int r = 0; for( int[] t : indices ) { Ssortingng items = ""; int sum = 0; for( int index : t ) { int value = values[index]; if( ! items.isEmpty()) { items += ", "; } items += index + ":" + value; sum += value; } System.out.println( "S" + ++r + " (" + sum + ") : " + items ); } } public static void main( Ssortingng[] args ) { int[] values = { 9, 18, 7, 8, 4, 9, 11, 15, 3, 8 }; List< int[] > indices = new LinkedList<>(); knapsack( 20, values, indices ); print( values, indices ); } } 

Le résultat:

 S1 (18) : 1:18 S2 (19) : 7:15, 4:4 S3 (20) : 6:11, 0:9 S4 (20) : 5:9, 3:8, 8:3 S5 (15) : 9:8, 2:7