arrays - resueltos - seleccionar elementos de una matriz matlab

divide una matriz en dos conjuntos con una diferencia mínima

Question

Una pregunta de entrevista que encontré:

Dado un conjunto de números, divida los números en dos conjuntos de modo que la diferencia entre la suma de los números en dos conjuntos sea mínima.

Esta es la idea que tengo, pero no estoy seguro si esta es una solución correcta:

1. ordenar la matriz
2. Tome los primeros 2 elementos..considérelos como 2 juegos (cada uno con 1 elemento)
3. Toma el siguiente elemento de la matriz.
4. Ahora decida en qué conjunto debe ir este elemento (calculando la suma ... debe ser mínimo)
5. repetir

¿Es esta la solución correcta? ¿Podemos hacerlo mejor?

Answer 1

¿Está ordenando su subconjunto en orden descendente o ascendente?

Piénselo así, la matriz {1, 3, 5, 8, 9, 25}

si tuviera que dividir, tendría {1,8,9} = 18 {3,5,25} = 33

Si estuviera ordenado en orden descendente, funcionaría mucho mejor

{25,1} = 26 {9,8,5,3} = 25

Entonces su solución es básicamente correcta, solo necesita asegurarse de tomar los valores más grandes primero.

EDITAR: Lee la publicación de tskuzzy. El mío no funciona

Answer 2

Comience a sumar números, pero cada vez compare la suma con el siguiente número. Si la suma es más o igual, mueva el número a otra matriz.

Ahora, para los siguientes números, cambia directamente a otra matriz, a menos que nueva suma <primera suma, y ​​luego puedas repetir el mismo proceso en los números restantes. De esta forma, terminaremos resolviendo tu problema en una sola iteración.

Si la matriz contiene números negativos arriba, no funcionará.

Answer 3

El problema que está describiendo es el problema de la partición . Encontrar una solución óptima es NP completo, sin embargo, hay una serie de aproximaciones que son casi perfectas para la mayoría de los casos.

De hecho, el algoritmo que describió es la forma en que los niños del patio de recreo elegirían equipos. Este algoritmo codicioso funciona notablemente bien si los números en el conjunto son de órdenes de magnitud similares. Claro, no es la mejor solución, pero considerando cómo el problema es NP-completo, es bastante bueno por su simplicidad.

Este artículo en American Scientist ofrece un excelente análisis del problema y debes leerlo: El problema difícil más fácil .

Answer 4

No, eso no funciona. No hay una solución de tiempo polinomial (a menos que P = NP). Lo mejor que puedes hacer es mirar todos los subconjuntos diferentes ...

http://en.wikipedia.org/wiki/Subset_sum_problem

Considere la lista [0,1,5,6].

Reivindicarás {0,5} y {1,6} cuando la mejor respuesta sea en realidad {0,1,5} y {6}

Answer 5

Un pequeño cambio: invierta el orden - comience con el número más grande y trabaje hacia abajo. Esto minimizará el error.

Answer 6

Después de pensarlo mucho y combinarlo, he encontrado la siguiente solución.

1. Sort and add elements at the same time.(To reduce one more iteration on array.)
2. Do (Sum/2) and find out median of sorted array (array/2)(median can be used to optimize more)
3. Pick up highest and lowest one by one until its near or equal to (sum/2)

Esta solución también funcionará para valores negativos.

Answer 7

Combinaciones sobre el enfoque de combinaciones:

import itertools as it

def min_diff_sets(data):
    """
        Parameters:
        - `data`: input list.
        Return:
        - min diff between sum of numbers in two sets
    """

    if len(data) == 1:
        return data[0]
    s = sum(data)
    # `a` is list of all possible combinations of all possible lengths (from 1
    # to len(data) )
    a = []
    for i in range(1, len(data)):
        a.extend(list(it.combinations(data, i)))
    # `b` is list of all possible pairs (combinations) of all elements from `a`
    b = it.combinations(a, 2)
    # `c` is going to be final correct list of combinations.
    # Let''s apply 2 filters:
    # 1. leave only pairs where: sum of all elements == sum(data)
    # 2. leave only pairs where: flat list from pairs == data
    c = filter(lambda x: sum(x[0])+sum(x[1])==s, b)
    c = filter(lambda x: sorted([i for sub in x for i in sub])==sorted(data), c)
    # `res` = [min_diff_between_sum_of_numbers_in_two_sets,
    #           ((set_1), (set_2))
    #         ]
    res = sorted([(abs(sum(i[0]) - sum(i[1])), i) for i in c],
            key=lambda x: x[0])
    return min([i[0] for i in res])

if __name__ == ''__main__'':
    assert min_diff_sets([10, 10]) == 0, "1st example"
    assert min_diff_sets([10]) == 10, "2nd example"
    assert min_diff_sets([5, 8, 13, 27, 14]) == 3, "3rd example"
    assert min_diff_sets([5, 5, 6, 5]) == 1, "4th example"
    assert min_diff_sets([12, 30, 30, 32, 42, 49]) == 9, "5th example"
    assert min_diff_sets([1, 1, 1, 3]) == 0, "6th example"

Answer 8

int ModDiff(int a, int b)
{
    if(a < b)return b - a;
    return a-b;
}

int EqDiv(int *a, int l, int *SumI, int *SumE)
{
    static int tc = 0;
    int min = ModDiff(*SumI,*SumE);
    for(int i = 0; i < l; i++)
    {
            swap(a,0,i);
            a++;
            int m1 = EqDiv(a, l-1, SumI,SumE);
            a--;
            swap(a,0,i);

            *SumI = *SumI + a[i];
            *SumE = *SumE - a[i];
            swap(a,0,i);
            a++;
            int m2 = EqDiv(a,l-1, SumI,SumE);
            a--;
            swap(a,0,i);
            *SumI = *SumI - a[i];
            *SumE = *SumE + a[i];

            min = min3(min,m1,m2);

    }
    return min;

}

llama a la función con SumI = 0 y SumE = suma de todos los elementos en a. Esta solución O (n!) Calcula la forma en que podemos dividir la matriz dada en 2 partes, por lo que la diferencia es mínima. Pero definitivamente no es práctico debido a la n! complejidad de tiempo buscando mejorar esto usando DP.

Answer 9

Prueba esto :

 partition(i, A, B) = min(partition(i+1, A U A[i], B),
                          partition(i+1, A, B U A[i])) where i< n  
                      Absolute(Sigma(A) - Sigma(B)) where i = n                                                

  n : number of elements in Original Array

Answer 10

Por favor, compruebe esta lógica que he escrito para este problema. Funcionó para algunos escenarios que revisé. Comente sobre la solución, Enfoque:

1. Clasifica la matriz principal y divídela en 2 equipos.
2. Luego comience a hacer que el equipo sea igual por turno e intercambie elementos de una matriz a otra, según las condiciones mencionadas en el código.

Si la diferencia es la diferencia de suma es menor que el número mínimo de la matriz más grande (matriz con mayor suma), a continuación, cambie los elementos de la matriz más grande a una matriz más pequeña. El cambio ocurre con la condición, ese elemento de la matriz más grande con un valor menor o igual a la diferencia. Cuando todos los elementos de la matriz más grande son mayores que la diferencia, el cambio se detiene y se produce el intercambio. Simplemente estoy intercambiando los últimos elementos de la matriz (se puede hacer más eficiente al encontrar qué dos elementos intercambiar), pero aún así funcionó. Avíseme si esta lógica falló en cualquier escenario.

public class SmallestDifference {
static int sum1 = 0, sum2 = 0, diff, minDiff;
private static List<Integer> minArr1;
private static List<Integer> minArr2;
private static List<Integer> biggerArr;

/**
 * @param args
 */
public static void main(String[] args) {
    SmallestDifference sm = new SmallestDifference();
    Integer[] array1 = { 2, 7, 1, 4, 5, 9, 10, 11 };
    List<Integer> array = new ArrayList<Integer>();
    for (Integer val : array1) {
        array.add(val);
    }
    Collections.sort(array);
    CopyOnWriteArrayList<Integer> arr1 = new CopyOnWriteArrayList<>(array.subList(0, array.size() / 2));
    CopyOnWriteArrayList<Integer> arr2 = new CopyOnWriteArrayList<>(array.subList(array.size() / 2, array.size()));
    diff = Math.abs(sm.getSum(arr1) - sm.getSum(arr2));
    minDiff = array.get(0);
    sm.updateSum(arr1, arr2);
    System.out.println(arr1 + " : " + arr2);
    System.out.println(sum1 + " - " + sum2 + " = " + diff + " : minDiff = " + minDiff);
    int k = arr2.size();
    biggerArr = arr2;
    while (diff != 0 && k >= 0) {
        while (diff != 0 && sm.findMin(biggerArr) < diff) {
            sm.swich(arr1, arr2);
            int sum1 = sm.getSum(arr1), sum2 = sm.getSum(arr2);
            diff = Math.abs(sum1 - sum2);
            if (sum1 > sum2) {
                biggerArr = arr1;
            } else {
                biggerArr = arr2;
            }
            if (minDiff > diff || sm.findMin(biggerArr) > diff) {
                minDiff = diff;
                minArr1 = new CopyOnWriteArrayList<>(arr1);
                minArr2 = new CopyOnWriteArrayList<>(arr2);
            }
            sm.updateSum(arr1, arr2);
            System.out.println("Shifting : " + sum1 + " - " + sum2 + " = " + diff + " : minDiff = " + minDiff);
        }
        while (k >= 0 && minDiff > array.get(0) && minDiff != 0) {
            sm.swap(arr1, arr2);
            diff = Math.abs(sm.getSum(arr1) - sm.getSum(arr2));
            if (minDiff > diff) {
                minDiff = diff;
                minArr1 = new CopyOnWriteArrayList<>(arr1);
                minArr2 = new CopyOnWriteArrayList<>(arr2);
            }
            sm.updateSum(arr1, arr2);
            System.out.println("Swapping : " + sum1 + " - " + sum2 + " = " + diff + " : minDiff = " + minDiff);
            k--;
        }
        k--;
    }
    System.out.println(minArr1 + " : " + minArr2 + " = " + minDiff);
}

private void updateSum(CopyOnWriteArrayList<Integer> arr1, CopyOnWriteArrayList<Integer> arr2) {
    SmallestDifference sm1 = new SmallestDifference();
    sum1 = sm1.getSum(arr1);
    sum2 = sm1.getSum(arr2);
}

private int findMin(List<Integer> biggerArr2) {
    Integer min = biggerArr2.get(0);
    for (Integer integer : biggerArr2) {
        if(min > integer) {
            min = integer;
        }
    }
    return min;
}

private int getSum(CopyOnWriteArrayList<Integer> arr) {
    int sum = 0;
    for (Integer val : arr) {
        sum += val;
    }
    return sum;
}

private void swap(CopyOnWriteArrayList<Integer> arr1, CopyOnWriteArrayList<Integer> arr2) {
    int l1 = arr1.size(), l2 = arr2.size(), temp2 = arr2.get(l2 - 1), temp1 = arr1.get(l1 - 1);
    arr1.remove(l1 - 1);
    arr1.add(temp2);
    arr2.remove(l2 - 1);
    arr2.add(temp1);
    System.out.println(arr1 + " : " + arr2);
}

private void swich(CopyOnWriteArrayList<Integer> arr1, CopyOnWriteArrayList<Integer> arr2) {
    Integer e;
    if (sum1 > sum2) {
        e = this.findElementJustLessThanMinDiff(arr1);
        arr1.remove(e);
        arr2.add(e);
    } else {
        e = this.findElementJustLessThanMinDiff(arr2);
        arr2.remove(e);
        arr1.add(e);
    }
    System.out.println(arr1 + " : " + arr2);
}

private Integer findElementJustLessThanMinDiff(CopyOnWriteArrayList<Integer> arr1) {
    Integer e = arr1.get(0);
    int tempDiff = diff - e;
    for (Integer integer : arr1) {
        if (diff > integer && (diff - integer) < tempDiff) {
            e = integer;
            tempDiff = diff - e;
        }
    }
    return e;
}

}

Answer 11

Esta es una variación del problema de la suma de mochilas y subconjuntos. En el problema de suma de subconjuntos, dados n enteros positivos y un valor k, tenemos que encontrar la suma del subconjunto cuyo valor es menor o igual a k. En el problema anterior hemos dado una matriz, aquí tenemos que encontrar el subconjunto cuya suma es menor o igual que total_sum (suma de valores de matriz). Por lo tanto, la suma del subconjunto se puede encontrar usando una variación en el algoritmo de mochila, tomando las ganancias como valores de matriz dados. Y la respuesta final es total_sum-dp [n] [total_sum / 2]. Eche un vistazo al código a continuación para una comprensión clara.

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
        int n;
        cin>>n;
        int arr[n],sum=0;
        for(int i=1;i<=n;i++)
        cin>>arr[i],sum+=arr[i];
        int temp=sum/2;
        int dp[n+1][temp+2];
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=temp;j++)
            {
                if(i==0 || j==0)
                dp[i][j]=0;
                else if(arr[i]<=j)
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-arr[i]]+arr[i]);
                else
                {
                dp[i][j]=dp[i-1][j];
                }
            }
        }
        cout<<sum-2*dp[n][temp]<<endl;
}

Answer 12

#include<bits/stdc++.h>
using namespace std;
bool ison(int i,int x)
{
 if((i>>x) & 1)return true;
 return false;
}
int main()
{
// cout<<"enter the number of elements  : ";
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    cin>>a[i];
    int sumarr1[(1<<n)-1];
    int sumarr2[(1<<n)-1];
    memset(sumarr1,0,sizeof(sumarr1));
    memset(sumarr2,0,sizeof(sumarr2));
    int index=0;
    vector<int>v1[(1<<n)-1];
    vector<int>v2[(1<<n)-1];

    for(int i=1;i<(1<<n);i++)
    {  
       for(int j=0;j<n;j++)
       {
          if(ison(i,j))
          {
             sumarr1[index]+=a[j];
             v1[index].push_back(a[j]);
          }
          else
          {
             sumarr2[index]+=a[j];
             v2[index].push_back(a[j]);
          }
       }index++;
    }
    int ans=INT_MAX;
    int ii;
    for(int i=0;i<index;i++)
    {
       if(abs(sumarr1[i]-sumarr2[i])<ans)
       {
          ii=i;
          ans=abs(sumarr1[i]-sumarr2[i]);
       }
    }
    cout<<"first partitioned array : ";
    for(int i=0;i<v1[ii].size();i++)
    {
       cout<<v1[ii][i]<<" ";
    }
    cout<<endl;
    cout<<"2nd partitioned array : ";
    for(int i=0;i<v2[ii].size();i++)
    {
       cout<<v2[ii][i]<<" ";
    }
    cout<<endl;
    cout<<"minimum difference is : "<<ans<<endl;
}

Answer 13

HI I think This Problem can be solved in Linear Time on a sorted array , no Polynomial Time is required , rather than Choosing Next Element u can choose nest two Element and decide which side which element to go. in This Way
in this way minimize the difference, let suppose
{0,1,5,6} ,
choose {0,1}
{0} , {1}
choose 5,6
{0,6}, {1,5}
but still that is not exact solution , now at the end there will be difference of sum in 2 array let suppose x
but there can be better solution of difference of (less than x)
for that Find again 1 greedy approach over  sorted half sized array
and move x/2(or nearby) element from 1 set to another or exchange element of(difference x/2) so that difference can be minimized***

Answer 14

Esto se puede resolver usando BST.
Primero ordena la matriz, di arr1
Para comenzar crea otro arr2 con el último elemento de arr1 (elimina este ele de arr1)

Ahora: repite los pasos hasta que no ocurra ningún intercambio.

1. Verifique arr1 para un elemento que pueda moverse a arr2 usando BST de modo que la diferencia sea menor a la diferencia mínima encontrada hasta ahora.
2. si encontramos un elemento, mueva este elemento a arr2 y vaya al paso 1 nuevamente.
3. si no encontramos ningún elemento en los pasos anteriores, realice los pasos 1 y 2 para arr2 y arr1. es decir, ahora compruebe si tenemos algún elemento en arr2 que se pueda mover a arr1
4. continúe con los pasos 1-4 hasta que no necesitemos ningún intercambio.
5. tenemos la solución

Ejemplo de código de Java:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Divide an array so that the difference between these 2 is min
 * 
 * @author shaikhjamir
 *
 */
public class DivideArrayForMinDiff {

    /**
     * Create 2 arrays and try to find the element from 2nd one so that diff is
     * min than the current one
     */

    private static int sum(List<Integer> arr) {

        int total = 0;
        for (int i = 0; i < arr.size(); i++) {
            total += arr.get(i);
        }

        return total;
    }

    private static int diff(ArrayList<Integer> arr, ArrayList<Integer> arr2) {
        int diff = sum(arr) - sum(arr2);
        if (diff < 0)
            diff = diff * -1;
        return diff;
    }

    private static int MIN = Integer.MAX_VALUE;

    private static int binarySearch(int low, int high, ArrayList<Integer> arr1, int arr2sum) {

        if (low > high || low < 0)
            return -1;

        int mid = (low + high) / 2;
        int midVal = arr1.get(mid);

        int sum1 = sum(arr1);
        int resultOfMoveOrg = (sum1 - midVal) - (arr2sum + midVal);
        int resultOfMove = (sum1 - midVal) - (arr2sum + midVal);
        if (resultOfMove < 0)
            resultOfMove = resultOfMove * -1;

        if (resultOfMove < MIN) {
            // lets do the swap
            return mid;
        }

        // this is positive number greater than min
        // which mean we should move left
        if (resultOfMoveOrg < 0) {

            // 1,10, 19 ==> 30
            // 100
            // 20, 110 = -90
            // 29, 111 = -83
            return binarySearch(low, mid - 1, arr1, arr2sum);
        } else {

            // resultOfMoveOrg > 0
            // 1,5,10, 15, 19, 20 => 70
            // 21
            // For 10
            // 60, 31 it will be 29
            // now if we move 1
            // 71, 22 ==> 49
            // but now if we move 20
            // 50, 41 ==> 9
            return binarySearch(mid + 1, high, arr1, arr2sum);
        }
    }

    private static int findMin(ArrayList<Integer> arr1) {

        ArrayList<Integer> list2 = new ArrayList<>(arr1.subList(arr1.size() - 1, arr1.size()));
        arr1.remove(arr1.size() - 1);
        while (true) {

            int index = binarySearch(0, arr1.size(), arr1, sum(list2));
            if (index != -1) {
                int val = arr1.get(index);
                arr1.remove(index);
                list2.add(val);
                Collections.sort(list2);
                MIN = diff(arr1, list2);
            } else {
                // now try for arr2
                int index2 = binarySearch(0, list2.size(), list2, sum(arr1));
                if (index2 != -1) {

                    int val = list2.get(index2);
                    list2.remove(index2);
                    arr1.add(val);
                    Collections.sort(arr1);

                    MIN = diff(arr1, list2);
                } else {
                    // no switch in both the cases
                    break;
                }
            }
        }

        System.out.println("MIN==>" + MIN);
        System.out.println("arr1==>" + arr1 + ":" + sum(arr1));
        System.out.println("list2==>" + list2 + ":" + sum(list2));
        return 0;
    }

    public static void main(String args[]) {

        ArrayList<Integer> org = new ArrayList<>();
        org = new ArrayList<>();
        org.add(1);
        org.add(2);
        org.add(3);
        org.add(7);
        org.add(8);
        org.add(10);

        findMin(org);
    }
}

Answer 15

Se mencionaron muchas respuestas sobre cómo obtener una solución "aproximada" en un plazo muy aceptable. Pero como se pregunta en una entrevista, no creo que necesiten un algoritmo de aproximación. Además, tampoco espero que necesiten un ingenuo algoritmo exponencial.

Al llegar al problema, suponiendo que se conoce el valor máximo de suma de números, de hecho puede resolverse en tiempo polinomial utilizando programación dinámica. Consulte este enlace https://people.cs.clemson.edu/~bcdean/dp_practice/dp_4.swf

Answer 16

Una posible solución aquí- https://.com/a/31228461/4955513 Este programa Java parece resolver este problema, siempre que se cumpla una condición: que hay una y única solución para el problema.