arrays - resueltos - vectores y matrices en programacion
¿Cómo dividir de forma óptima una matriz en dos subgrupos para que la suma de los elementos en ambos sea la misma? De lo contrario, ¿se produce un error? (17)
¿Cómo dividir de forma óptima una matriz en dos subarrays para que la suma de elementos en ambas subarrays sea la misma, de lo contrario, dé un error?
Ejemplo 1
Dada la matriz
10, 20 , 30 , 5 , 40 , 50 , 40 , 15
Se puede dividir como
10, 20, 30, 5, 40
y
50, 40, 15
Cada subarreglo suma hasta 105.
Ejemplo 2
10, 20, 30, 5, 40, 50, 40, 10
La matriz no se puede dividir en 2 matrices de igual suma.
Algoritmo:
Paso 1) Divide la matriz en dos
Paso 2) Si la suma es igual, se completa la división
Paso 3) Intercambia un elemento de array1 con array2, guiado por las cuatro reglas:
SI la suma de elementos en array1 es menor que la suma de elementos en array2
Regla 1:
Encuentre un número en array1 que sea más pequeño que un número en array2 de tal manera que el intercambio de estos elementos, no incremente la suma de array1 más allá de la suma esperada. Si lo encuentra, intercambie los elementos y regrese.
Regla 2:
Si no se cumple la Regla1, encuentre un número en la matriz1 que sea mayor que un número en la matriz2 de tal manera que la diferencia entre dos números cualquiera en la matriz1 y la matriz2 no sea menor que la diferencia entre estos dos números.
MÁS
Regla 3:
Encuentre un número en la matriz1 que sea más grande que un número en la matriz2 de tal manera que al intercambiar estos elementos, no disminuya la suma de la matriz1 más allá de la suma esperada. Si lo encuentra, cambie la
Elementos y retorno.
Regla 4:
Si no se cumple con Rule3, encuentre un número en array1 que sea menor que un número en array2 de tal manera que la diferencia entre dos números cualquiera en array1 y array2 no sea menor que la diferencia entre estos dos números.
Paso 5) Vaya al Paso 2 hasta que el intercambio dé como resultado una matriz con el mismo conjunto de elementos que ya se encuentra en Setp 6) Si se produce una repetición, esta matriz no se puede dividir en dos mitades con la misma suma. El conjunto actual de matrices O el conjunto que se formó justo antes de esta repetición debería ser la mejor división de la matriz.
Nota: El enfoque adoptado es cambiar el elemento de una matriz a otra de tal manera que la suma resultante sea tan cercana a la suma esperada.
El programa java está disponible en Java Code.
El problema @Gal Subset-Sum es NP-Complete y tiene un algoritmo de programación dinámica pseudo-polinomial O (n * TotalSum). Pero este problema no es NP-Completo. Este es un caso especial y, de hecho, se puede resolver en tiempo lineal.
Aquí estamos buscando un índice donde podamos dividir la matriz en dos partes con la misma suma. Compruebe el siguiente código.
Análisis: O (n), ya que el algoritmo solo itera a través de la matriz y no usa TotalSum.
public class EqualSumSplit {
public static int solution( int[] A ) {
int[] B = new int[A.length];
int[] C = new int[A.length];
int sum = 0;
for (int i=0; i< A.length; i++) {
sum += A[i];
B[i] = sum;
// System.out.print(B[i]+" ");
}
// System.out.println();
sum = 0;
for (int i=A.length-1; i>=0; i--) {
sum += A[i];
C[i] = sum;
// System.out.print(C[i]+" ");
}
// System.out.println();
for (int i=0; i< A.length-1; i++) {
if (B[i] == C[i+1]) {
System.out.println(i+" "+B[i]);
return i;
}
}
return -1;
}
public static void main(String args[] ) {
int[] A = {-7, 1, 2, 3, -4, 3, 0};
int[] B = {10, 20 , 30 , 5 , 40 , 50 , 40 , 15};
solution(A);
solution(B);
}
}
En su variante común, este problema impone 2 restricciones y se puede hacer de una manera más fácil.
- Si la partición solo se puede realizar en algún lugar a lo largo de la matriz (no consideramos los elementos fuera de orden)
- No hay números negativos.
El algoritmo que funciona entonces podría ser:
- Tener 2 variables, leftSum y rightSum.
- Comience incrementando leftSum desde la izquierda y rightSum desde la derecha de la matriz.
- Intenta corregir cualquier desequilibrio en él.
El siguiente código hace lo anterior:
public boolean canBalance(int[] nums) {
int leftSum = 0, rightSum = 0, i, j;
if(nums.length == 1)
return false;
for(i=0, j=nums.length-1; i<=j ;){
if(leftSum <= rightSum){
leftSum+=nums[i];
i++;
}else{
rightSum+=nums[j];
j--;
}
}
return (rightSum == leftSum);
}
La salida:
canBalance({1, 1, 1, 2, 1}) → true OK
canBalance({2, 1, 1, 2, 1}) → false OK
canBalance({10, 10}) → true OK
canBalance({1, 1, 1, 1, 4}) → true OK
canBalance({2, 1, 1, 1, 4}) → false OK
canBalance({2, 3, 4, 1, 2}) → false OK
canBalance({1, 2, 3, 1, 0, 2, 3}) → true OK
canBalance({1, 2, 3, 1, 0, 1, 3}) → false OK
canBalance({1}) → false OK
canBalance({1, 1, 1, 2, 1}) → true OK
Por supuesto, si los elementos pueden combinarse fuera de orden, se convierte en un problema de partición con toda su complejidad.
Esta es una solución recursiva al problema, una solución no recursiva podría usar un método auxiliar para obtener la suma de los índices 0 a un índice actual en un bucle for y otra podría obtener la suma de todos los elementos del mismo índice actual para El fin, que funciona. Ahora, si desea obtener los elementos en una matriz y comparar la suma, primero encuentre el punto (índice) que marca el derrame donde la suma de ambos lados es igual, luego obtenga una lista y agregue los valores antes de ese índice y otra lista para ir después de ese índice.
Aquí está el mío (recursión), que solo determina si hay un lugar para dividir la matriz de modo que la suma de los números en un lado sea igual a la suma de los números en el otro lado. Preocuparse por indexOutOfBounds, que puede suceder fácilmente en una recursión, un pequeño error podría resultar fatal y producir muchas excepciones y errores.
public boolean canBalance(int[] nums) {
return (nums.length <= 1) ? false : canBalanceRecur(nums, 0);
}
public boolean canBalanceRecur(int[] nums, int index){ //recursive version
if(index == nums.length - 1 && recurSumBeforeIndex(nums, 0, index)
!= sumAfterIndex(nums, index)){ //if we get here and its still bad
return false;
}
if(recurSumBeforeIndex(nums, 0, index + 1) == sumAfterIndex(nums, index + 1)){
return true;
}
return canBalanceRecur(nums, index + 1); //move the index up
}
public int recurSumBeforeIndex(int[] nums, int start, int index){
return (start == index - 1 && start < nums.length)
? nums[start]
: nums[start] + recurSumBeforeIndex(nums, start + 1, index);
}
public int sumAfterIndex(int[] nums, int startIndex){
return (startIndex == nums.length - 1)
? nums[nums.length - 1]
: nums[startIndex] + sumAfterIndex(nums, startIndex + 1);
}
Este problema dice que si una matriz puede tener dos subarreglos con su suma de elementos igual. Así que un valor booleano debe ser devuelto. He encontrado un algoritmo eficiente: Algo: Procedimiento Paso 1: Tome una matriz vacía como contenedor, ordene la matriz inicial y manténgala en la vacía. Paso 2: ahora tome dos matrices asignables dinámicamente y saque la más alta y la segunda más alta de la matriz auxiliar y manténgala en las dos subarrays respectivamente, y elimínela de la matriz auxiliar. Paso 3: Compare la suma de elementos en los subarrays, la suma más pequeña tendrá la oportunidad de obtener el elemento restante más alto en la matriz y luego eliminarlo del contenedor. Paso 4: Repita el paso 3 hasta que el contenedor esté vacío. Paso 5: Compara la suma de dos subarreglos, si son iguales devuelve verdadero o falso.
// La complejidad de este problema es que puede haber muchas combinaciones posibles, pero este algo tiene una forma única.
Esto se llama problema de partición . Hay soluciones óptimas para algunos casos especiales. Sin embargo, en general, es un problema NP-completo.
Existe una solución, que involucra programación dinámica, que se ejecuta en O(n*TotalSum) , donde n es el número de elementos en la matriz y TotalSum es su suma total.
La primera parte consiste en calcular el conjunto de todos los números que se pueden crear agregando elementos a la matriz.
Para una matriz de tamaño n , llamaremos a esto T(n) ,
T(n) = T(n-1) UNION { Array[n]+k | k is in T(n-1) }
(La prueba de corrección es por inducción, como en la mayoría de los casos de funciones recursivas).
Además, recuerde para cada celda en la matriz dinámica, los elementos que se agregaron para crearla.
El análisis de complejidad simple mostrará que esto se hace en O(n*TotalSum) .
Después de calcular T(n) , busque en el conjunto un elemento que TotalSum / 2 exactamente el tamaño de TotalSum / 2 .
Si tal elemento existe, entonces los elementos que lo crearon, sumados, igual a TotalSum / 2 , y los elementos que no formaron parte de su creación también son iguales a TotalSum / 2 ( TotalSum - TotalSum / 2 = TotalSum / 2 ).
Esta es una solución pseudo-polinomial. AFAIK, no se sabe que este problema esté en P.
Intenté una solución diferente. aparte de las soluciones Wiki (problema de partición).
static void subSet(int array[]) {
System.out.println("Input elements :" + Arrays.toString(array));
int sum = 0;
for (int element : array) {
sum = sum + element;
}
if (sum % 2 == 1) {
System.out.println("Invalid Pair");
return;
}
Arrays.sort(array);
System.out.println("Sorted elements :" + Arrays.toString(array));
int subSum = sum / 2;
int[] subSet = new int[array.length];
int tmpSum = 0;
boolean isFastpath = true;
int lastStopIndex = 0;
for (int j = array.length - 1; j >= 0; j--) {
tmpSum = tmpSum + array[j];
if (tmpSum == subSum) { // if Match found
if (isFastpath) { // if no skip required and straight forward
// method
System.out.println("Found SubSets 0..." + (j - 1) + " and "
+ j + "..." + (array.length - 1));
} else {
subSet[j] = array[j];
array[j] = 0;
System.out.println("Found..");
System.out.println("Set 1" + Arrays.toString(subSet));
System.out.println("Set 2" + Arrays.toString(array));
}
return;
} else {
// Either the tmpSum greater than subSum or less .
// if less , just look for next item
if (tmpSum < subSum && ((subSum - tmpSum) >= array[0])) {
if (lastStopIndex > j && subSet[lastStopIndex] == 0) {
subSet[lastStopIndex] = array[lastStopIndex];
array[lastStopIndex] = 0;
}
lastStopIndex = j;
continue;
}
isFastpath = false;
if (subSet[lastStopIndex] == 0) {
subSet[lastStopIndex] = array[lastStopIndex];
array[lastStopIndex] = 0;
}
tmpSum = tmpSum - array[j];
}
}
}
He probado. (Funciona bien con un número positivo mayor que 0). Avísenme si hay algún problema.
Me hicieron esta pregunta en una entrevista, y proporcioné la siguiente solución simple, ya que NO había visto este problema en ningún sitio web anteriormente.
Digamos Array A = {45,10,10,10,10,5} Luego, la división será en el índice = 1 (índice basado en 0), de modo que tengamos dos conjuntos de suma iguales {45} y {10,10 10,10,5}
int leftSum = A[0], rightSum = A[A.length - 1];
int currentLeftIndex = 0; currentRightIndex = A.length - 1
/ * Mueva los dos punteros de índice hacia la mitad de la matriz hasta currentRightIndex! = CurrentLeftIndex. Aumente leftIndex si la suma de los elementos de la izquierda es aún menor o igual que la suma de los elementos en la derecha de ''rightIndex''. Al final, verifique si leftSum == rightSum. Si es verdadero, obtuvimos el índice como currentLeftIndex + 1 (o simplemente currentRightIndex, ya que currentRightIndex será igual a currentLeftIndex + 1 en este caso). * /
while (currentLeftIndex < currentRightIndex)
{
if ( currentLeftIndex+1 != currentRightIndex && (leftSum + A[currentLeftIndex + 1) <=currentRightSum )
{
currentLeftIndex ++;
leftSum = leftSum + A[currentLeftIndex];
}
if ( currentRightIndex - 1 != currentLeftIndex && (rightSum + A[currentRightIndex - 1] <= currentLeftSum)
{
currentRightIndex --;
rightSum = rightSum + A[currentRightIndex];
}
}
if (CurrentLeftIndex == currentRightIndex - 1 && leftSum == rightSum)
PRINT("got split point at index "+currentRightIndex);
Por favor prueba esto y hazme saber si no funciona. Espero que te ayude.
static ArrayList<Integer> array = null;
public static void main(String[] args) throws IOException {
ArrayList<Integer> inputArray = getinputArray();
System.out.println("inputArray is " + inputArray);
Collections.sort(inputArray);
int totalSum = 0;
Iterator<Integer> inputArrayIterator = inputArray.iterator();
while (inputArrayIterator.hasNext()) {
totalSum = totalSum + inputArrayIterator.next();
}
if (totalSum % 2 != 0) {
System.out.println("Not Possible");
return;
}
int leftSum = inputArray.get(0);
int rightSum = inputArray.get(inputArray.size() - 1);
int currentLeftIndex = 0;
int currentRightIndex = inputArray.size() - 1;
while (leftSum <= (totalSum / 2)) {
if ((currentLeftIndex + 1 != currentRightIndex)
&& leftSum != (totalSum / 2)) {
currentLeftIndex++;
leftSum = leftSum + inputArray.get(currentLeftIndex);
} else
break;
}
if (leftSum == (totalSum / 2)) {
ArrayList<Integer> splitleft = new ArrayList<Integer>();
ArrayList<Integer> splitright = new ArrayList<Integer>();
for (int i = 0; i <= currentLeftIndex; i++) {
splitleft.add(inputArray.get(i));
}
for (int i = currentLeftIndex + 1; i < inputArray.size(); i++) {
splitright.add(inputArray.get(i));
}
System.out.println("splitleft is :" + splitleft);
System.out.println("splitright is :" + splitright);
}
else
System.out.println("Not possible");
}
public static ArrayList<Integer> getinputArray() {
Scanner scanner = new Scanner(System.in);
array = new ArrayList<Integer>();
int size;
System.out.println("Enter the Initial array size : ");
size = scanner.nextInt();
System.out.println("Enter elements in the array");
for (int j = 0; j < size; j++) {
int element;
element = scanner.nextInt();
array.add(element);
}
return array;
}
}
Primero, si los elementos son enteros, verifique que el total sea divisible por dos, si no es un éxito no es posible.
Yo configuraría el problema como un árbol binario, con el nivel 0 decidiendo a qué elemento del conjunto 0 va, el nivel 1 decidiendo qué elemento del conjunto 1 entra, etc. En cualquier momento, si la suma de un conjunto es la mitad del total, usted '' hecho, éxito En cualquier momento, si la suma de un conjunto es más de la mitad del total, ese subárbol es un error y debe realizar una copia de seguridad. En ese punto es un problema de travesía de árboles.
Solución encontrada here
package sort;
import java.util.ArrayList;
import java.util.List;
public class ArraySumSplit {
public static void main (String[] args) throws Exception {
int arr[] = {1 , 2 , 3 , 4 , 5 , 5, 1, 1, 3, 2, 1};
split(arr);
}
static void split(int[] array) throws Exception {
int sum = 0;
for(int n : array) sum += n;
if(sum % 2 == 1) throw new Exception(); //impossible to split evenly
List<Integer> firstPart = new ArrayList<Integer>();
List<Integer> secondPart = new ArrayList<Integer>();
if(!dfs(0, sum / 2, array, firstPart, secondPart)) throw new Exception(); // impossible to split evenly;
//firstPart and secondPart have the grouped elements, print or return them if necessary.
System.out.print(firstPart.toString());
int sum1 = 0;
for (Integer val : firstPart) {
sum1 += val;
}
System.out.println(" = " + sum1);
System.out.print(secondPart.toString());
int sum2 = 0;
for (Integer val : secondPart) {
sum2 += val;
}
System.out.println(" = " + sum2);
}
static boolean dfs(int i, int limit, int[] array, List<Integer> firstPart, List<Integer> secondPart) {
if( limit == 0) {
for(int j = i; j < array.length; j++) {
secondPart.add(array[j]);
}
return true;
}
if(limit < 0 || i == array.length) {
return false;
}
firstPart.add(array[i]);
if(dfs(i + 1, limit - array[i], array, firstPart, secondPart)) return true;
firstPart.remove(firstPart.size() - 1);
secondPart.add(array[i]);
if(dfs(i + 1, limit, array, firstPart, secondPart)) return true;
secondPart.remove(secondPart.size() - 1);
return false;
}
}
Solución muy simple con recursión.
public boolean splitArray(int[] nums){
return arrCheck(0, nums, 0);
}
public boolean arrCheck(int start, int[] nums, int tot){
if(start >= nums.length) return tot == 0;
if(arrCheck(start+1, nums, tot+nums[start])) return true;
if(arrCheck(start+1, nums, tot-nums[start])) return true;
return false;
}
Una MAL heurística codiciosa para resolver este problema: intente clasificar la lista de menor a mayor, y divida esa lista en dos teniendo list1 = los elementos impares, y list2 = los elementos pares.
public boolean splitBetween(int[] x){
int sum=0;
int sum1=0;
if (x.length==1){
System.out.println("Not a valid value");
}
for (int i=0;i<x.length;i++){
sum=sum+x[i];
System.out.println(sum);
for (int j=i+1;j<x.length;j++){
sum1=sum1+x[j];
System.out.println("SUm1:"+sum1);
}
if(sum==sum1){
System.out.println("split possible");
System.out.println("Sum: " +sum +" Sum1:" + sum1);
return true;
}else{
System.out.println("Split not possible");
}
sum1=0;
}
return false;
}
package PACKAGE1;
import java.io.*;
import java.util.Arrays;
public class programToSplitAnArray {
public static void main(String args[]) throws NumberFormatException,
IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("enter the no. of elements to enter");
int n = Integer.parseInt(br.readLine());
int x[] = new int[n];
int half;
for (int i = 0; i < n; i++) {
x[i] = Integer.parseInt(br.readLine());
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum = sum + x[i];
}
if (sum % 2 != 0) {
System.out.println("the sum is odd and cannot be divided");
System.out.println("The sum is " + sum);
}
else {
boolean div = false;
half = sum / 2;
int sum1 = 0;
for (int i = 0; i < n; i++) {
sum1 = sum1 + x[i];
if (sum1 == half) {
System.out.println("array can be divided");
div = true;
break;
}
}
if (div == true) {
int t = 0;
int[] array1 = new int[n];
int count = 0;
for (int i = 0; i < n; i++) {
t = t + x[i];
if (t <= half) {
array1[i] = x[i];
count++;
}
}
array1 = Arrays.copyOf(array1, count);
int array2[] = new int[n - count];
int k = 0;
for (int i = count; i < n; i++) {
array2[k] = x[i];
k++;
}
System.out.println("The first array is ");
for (int m : array1) {
System.out.println(m);
}
System.out.println("The second array is ");
for (int m : array2) {
System.out.println(m);
}
} else {
System.out.println("array cannot be divided");
}
}
}
}
public class Problem1 {
public static void main(String[] args) throws IOException{
Scanner scanner=new Scanner(System.in);
ArrayList<Integer> array=new ArrayList<Integer>();
int cases;
System.out.println("Enter the test cases");
cases=scanner.nextInt();
for(int i=0;i<cases;i++){
int size;
size=scanner.nextInt();
System.out.println("Enter the Initial array size : ");
for(int j=0;j<size;j++){
System.out.println("Enter elements in the array");
int element;
element=scanner.nextInt();
array.add(element);
}
}
if(validate(array)){
System.out.println("Array can be Partitioned");}
else{
System.out.println("Error");}
}
public static boolean validate(ArrayList<Integer> array){
boolean flag=false;
Collections.sort(array);
System.out.println(array);
int index=array.size();
ArrayList<Integer> sub1=new ArrayList<Integer>();
ArrayList<Integer> sub2=new ArrayList<Integer>();
sub1.add(array.get(index-1));
array.remove(index-1);
index=array.size();
sub2.add(array.get(index-1));
array.remove(index-1);
while(!array.isEmpty()){
if(compareSum(sub1,sub2)){
index=array.size();
sub2.add(array.get(index-1));
array.remove(index-1);
}
else{
index=array.size();
sub1.add(array.get(index-1));
array.remove(index-1);
}
}
if(sumOfArray(sub1).equals(sumOfArray(sub2)))
flag=true;
else
flag=false;
return flag;
}
public static Integer sumOfArray(ArrayList<Integer> array){
Iterator<Integer> it=array.iterator();
Integer sum=0;
while(it.hasNext()){
sum +=it.next();
}
return sum;
}
public static boolean compareSum(ArrayList<Integer> sub1,ArrayList<Integer> sub2){
boolean flag=false;
int sum1=sumOfArray(sub1);
int sum2=sumOfArray(sub2);
if(sum1>sum2)
flag=true;
else
flag=false;
return flag;
}
}
// El enfoque codicioso //