Sumas más cercanas de 2 grupos en Java -- java campo con algorithm camp Relacionados El problema

Closest Sums of 2 groups in java


0
vote

problema

Español

Estoy teniendo algunos problemas resolviendo esta pregunta:

Dada una matriz de int S, divida la entrada en 2 grupos de manera que sus sumas son lo más cerca posible, los 2 grupos deben ser iguales en longitud, o si la entrada es de longitud impar entonces Un grupo puede tener 1 más que el otro. Luego, imprima primero la suma inferior, y la suma superior después.

ex: entrada - & gt; [4,6,17,3,2,5,10] Salida - & gt; 23,24 ([17,5,2] , [10,6,4,3])

Esto es lo que he llegado y, hasta ahora, lo que he probado ha pasado, pero no sé si realmente es correcto:

  public static String closestSums(int[] input) {     Integer sum1 = 0;     Integer sum2 = 0;     Integer dif = 0;     Integer bigSum = 0;      List<Integer> list = new ArrayList<>();     List<Integer> list1 = new ArrayList<>();     List<Integer> list2 = new ArrayList<>();      for (int x = 0; x < input.length; x++) {         list.add(input[x]);     }      Collections.sort(list);      for (int x = list.size(); x >= 0; x--) {         bigSum += list.get(x);         if (dif == 0) {             dif = list.get(x);             list2.add(list.get(x));         }         else if (dif > 0) {             dif -= list.get(x);             list1.add(list.get(x));         }         else {             dif += list.get(x);             list2.add(list.get(x));         }     }      dif = Math.abs(dif);     if (dif != 0) {         sum2 = (bigSum / 2) + dif;         sum1 = bigSum / 2;     }     else {         sum2 = bigSum / 2;         sum1 = bigSum / 2;     }     return sum1 + ", " + sum2; }   
Original en ingles

I'm having some problems solving this question:

Given an array of ints, divide the input into 2 groups such that their sums are as close as possible, the 2 groups must be equal in length, or if the input is odd length then one group can have 1 more than the other. Then print the lower sum first, and the higher sum after.

Ex: input -> [4,6,17,3,2,5,10] output -> 23,24 ([17,5,2] , [10,6,4,3])

This is what I've come up with and so far what I've tested it's passed but I do not know if it's actually correct:

public static String closestSums(int[] input) {     Integer sum1 = 0;     Integer sum2 = 0;     Integer dif = 0;     Integer bigSum = 0;      List<Integer> list = new ArrayList<>();     List<Integer> list1 = new ArrayList<>();     List<Integer> list2 = new ArrayList<>();      for (int x = 0; x < input.length; x++) {         list.add(input[x]);     }      Collections.sort(list);      for (int x = list.size(); x >= 0; x--) {         bigSum += list.get(x);         if (dif == 0) {             dif = list.get(x);             list2.add(list.get(x));         }         else if (dif > 0) {             dif -= list.get(x);             list1.add(list.get(x));         }         else {             dif += list.get(x);             list2.add(list.get(x));         }     }      dif = Math.abs(dif);     if (dif != 0) {         sum2 = (bigSum / 2) + dif;         sum1 = bigSum / 2;     }     else {         sum2 = bigSum / 2;         sum1 = bigSum / 2;     }     return sum1 + ", " + sum2; } 
     
       
       

Lista de respuestas

2
 
vote

no es correcto.

Independientemente del montón de errores de codificación pequeños que se mencionan en la otra respuesta, su algoritmo no funciona.

Considere la entrada [3, 3, 2, 2, 2] . Su algoritmo lo dividirá en [3, 2, 2] y [3, 2] Con una diferencia de 7-5=2 . Sin embargo, existe una división mejor con las sumas iguales: [3, 3] y [2, 2, 2] .

No voy a proporcionar un algoritmo completo, pero le daré algunos toques:

1 - La diferencia mínima puede ser buscada por binarios. Si puede llegar a un algoritmo que decide si es posible dividir la matriz para que la diferencia de las sumas de las piezas sea como máximo d para un determinado d , entonces puede buscar binary el mínimo d para el cual el algoritmo sale [3, 3, 2, 2, 2]0 .

2 - Mire la Problema de suma de subconjunto , puede ayudar con el subproblema que definí en el artículo 1.

 

It's not correct.

Regardless of the bunch of small coding mistakes that are mentioned in the other answer, your algorithm doesn't work.

Consider the input [3, 3, 2, 2, 2]. Your algorithm will divide it into [3, 2, 2] and [3, 2] with a difference of 7-5=2. However, a better split with equal sums exists: [3, 3] and [2, 2, 2].

I am not going to provide a complete algorithm but give you a few hints:

1 - The minimum difference can be binary-searched. If you can come up with an algorithm that decides whether it is possible to split the array so that the difference of the sums of the pieces is at most d for a given d, then you can binary search the minimum d for which the algorithm outputs 1.

2 - Look at the subset sum problem, it can help with the subproblem I defined in item 1.

 
 
 
 
1
 
vote

He hecho 3 observaciones después de analizar y amplificador; Ejecutando su código.

  1. Hay muchos errores pequeños en todo el código.

    • Error sintaxico en la línea 4 (inicialización de 'DIF') Línea 11 (la palabra clave 'para')
    • Error lógico en la línea 26, línea 27 (en lugar de acceder al índice 'I', debe acceder al índice 'x')
    • Error de tiempo de ejecución en la línea 17 (inicializando [3, 3, 2, 2, 2]1111 se lanzará un error de tiempo de ejecución [3, 3, 2, 2, 2]2 )

    , sin embargo, las cosas importantes que deben mirar, se mencionan a continuación

  2. Es una sugerencia , si no está imprimiendo la lista con el 'Sum1' y el amplificador; 'Sum2', luego creando y operando las otras dos listas de salida es redundante. Las sumas respectivas de la lista se pueden calcular mientras atraviesan la lista principal.

  3. Lo más importante , la forma en que está calculando suma1 y suma2 después de atravesar la lista y luego dividirlos, no es confiable. P.ej. La siguiente entrada le dará una salida inesperada [3, 3, 2, 2, 2]3 . Entonces, le sugiero que recurre a la forma más confiable de calcular la suma de la lista 1 & amp; Lista 2, que los está calculando mientras atraviesa la lista. (También puede eliminar la lógica completa de [3, 3, 2, 2, 2]4 )

Las últimas palabras: intente e implementa las ideas mencionadas anteriormente usted mismo.

 

I have made 3 observations after analyzing & running your Code.

  1. There lot of small errors throughout the code.

    • Syntaxical Error On Line 4 (Initialization of 'Dif') Line 11(The 'for' keyword)
    • Logical Error on Line 26, Line 27 (Instead of Accessing Index 'i', you must access index 'x')
    • Runtime Error on Line 17 (Initializing x=list.size() will throw a runtime error java.lang.IndexOutOfBoundsException)

    Though, the important things to look at, are mentioned below

  2. It's a suggestion, if you aren't printing the list with the 'sum1' & 'sum2', then creating and operating the two other output lists is redundant. The respective Sums of the list can be calculated while traversing the main list.

  3. Most importantly, the way you are calculating sum1 and sum2 after traversing the list and then dividing them, is not reliable. Eg. The Following input will give an unexpected output [4,6,45,3,2,5,10]. So, I suggest you to resort to the most reliable way of calculating the sum of list 1 & list 2, which is calculating them while traversing the list. (You may also remove the full logic of bigSum)

Last Words: Try and Implement the above mentioned Ideas yourself.

 
 

Relacionados problema

8  Fondo de partículas de WPF rápido  ( Fast wpf particle background ) 
Estoy construyendo una aplicación WPF y quiero que sus antecedentes se llenen con partículas con aleatorio: opacidad / z-orden tamaño Velocity " Fu...

24  Seguimiento: "Clasificación" de colores por carácter distintivo  ( Followup sorting colors by distinctiveness ) 
Pregunta original Si tiene colores máximos y lejanos (y algunas métricas de distancia asociada), ¿puede idear una manera de ordenar esos colores en algún ...

331  ¿Cuál es la forma más rápida de obtener el valor de π?  ( What is the fastest way to get the value of %cf%80 ) 
Estoy buscando la forma más rápida de obtener el valor de π, como un desafío personal. Más específicamente, estoy usando formas de que no impliquen el uso de ...

21  Obtener eficientemente obtener sumas ordenadas de una lista ordenada  ( Efficiently get sorted sums of a sorted list ) 
Tiene una lista ascendente de números, cuál es el algoritmo más eficiente que puede pensar para obtener la lista ascendente de sumas de cada dos números en es...

12  Diseñando un sistema de calendario como Google Calendar [CERRADO]  ( Designing a calendar system like google calendar ) 
cerrado . Esta pregunta debe ser más enfocado . Actualmente no está aceptando respuestas. ...

3  Usando tamizado para la realidad aumentada  ( Using sift for augmented reality ) 
Me he encontrado con muchas bibliotecas / SDK / API de AR, todos ellos están basados ​​en marcadores, hasta que encontré Este video , de la descripción y los...

70  Función para crear ruedas de color [cerrado]  ( Function for creating color wheels ) 
cerrado . Esta pregunta debe ser más enfocado . Actualmente no está aceptando respuestas. ...

8  Cerca de algoritmos de clasificación - ¿Cuándo usar?  ( Near sorting algorithms when to use ) 
De vez en cuando, navegue por la web y busco algoritmos interesantes y datos para poner en mi bolsa de trucos. Hace un año, me encontré con la Soft Heap Est...

61  Código más eficiente para los primeros 10000 números primos?  ( Most efficient code for the first 10000 prime numbers ) 
Quiero imprimir los primeros 10000 números primos. ¿Alguien puede darme el código más eficiente para esto? Aclaraciones: no importa si su código es inefici...

3  Stl __merge_without_buffer algoritmo?  ( Stl merge without buffer algorithm ) 
¿Dónde puedo obtener una descripción de alto nivel decente del algoritmo utilizado en __merge_without_buffer() en el STL de C ++? Estoy tratando de reembols...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos