Comment diviser un ensemble en deux sous-ensembles tels que la différence entre la somme des nombres dans deux ensembles est minime?

Étant donné un ensemble de nombres, divisez les nombres en deux sous-ensembles de sorte que la différence entre la somme des nombres dans deux sous-ensembles soit minime.

C'est L'idée que j'ai, mais je ne suis pas sûr que ce soit une solution correcte:

  1. Trier le tableau
  2. prenez les 2 premiers éléments. Considérez-les comme 2 ensembles (chacun ayant 1 élément)
  3. Prenez l'élément suivant du tableau.
  4. décidez dans quel ensemble cet élément devrait-il aller (en calculant la somme = > devrait être minimum)
  5. répéter

Est-ce la bonne solution? Pouvons-nous faire mieux?

46
demandé sur nbro 2011-07-06 17:27:59

13 réponses

Le décision version du problème que vous décrivez est un NP-complet problème et il est appelé la partition problème. Il existe un certain nombre d'approximations {[2] } qui fournissent, dans de nombreux cas, des solutions optimales ou, du moins, assez bonnes.

L'algorithme simple que vous avez décrit est une façon dont les enfants de terrain de jeu choisiraient des équipes. Cet algorithme gourmand fonctionne remarquablement bien si les nombres de l'ensemble sont d'ordres similaires de ampleur.

L'article la méthode La plus Simple Problème très difficile, par Scientifique Américain, donne une excellente analyse du problème. Vous devriez passer par et lire!

36
répondu tskuzzy 2018-03-03 13:48:17

Non, ça ne marche pas. Il n'y a pas de solution temporelle polynomiale (sauf si P=NP). Le mieux que vous pouvez faire est de regarder tous les différents sous-ensembles. Jetez un oeil au problème de somme du sous-ensemble .

Considérez la liste [0, 1, 5, 6]. Vous réclamera {0, 5} et {1, 6}, lorsque la meilleure réponse est en fait {0, 1, 5} et {6}.

8
répondu sshannin 2018-03-03 23:05:05

Combinaisons sur combinaisons approche:

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"
1
répondu user913624 2013-08-29 10:46:35

Un petit changement: Inverser l'ordre-commencer par le plus grand nombre et travailler vers le bas. Cela permettra de minimiser l'erreur.

0
répondu Ed Staub 2011-07-06 13:36:29

Triez-vous votre sous-ensemble en ordre décroissant ou croissant?

Penser comme ça, le tableau {1, 3, 5, 8, 9, 25}

Si vous divisez, vous auriez {1,8,9} =18 {3,5,25} =33

Si elle était triée dans l'ordre décroissant, cela fonctionnerait beaucoup mieux

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

Donc, votre solution est fondamentalement correcte, il suffit de s'assurer de prendre les plus grandes valeurs en premier.

Modifier: lire le post de tskuzzy. Le mien n'a pas travail

0
répondu Collecter 2011-07-06 14:09:07

C'est une variante du problème du sac à dos et de la somme des sous-ensembles. Dans le problème de la somme du sous-ensemble, étant donné n entiers positifs et une valeur k et nous devons trouver la somme du sous-ensemble dont la valeur est inférieure ou égale à K. Dans le problème ci-dessus, nous avons donné un tableau, ici nous devons trouver le sous-ensemble dont la somme est inférieure ou égale à total_sum(somme des valeurs du tableau). De sorte que le la somme du sous-ensemble peut être trouvée en utilisant une variation de l'algorithme knapsack, par prendre des bénéfices en tant que valeurs de tableau données. Et la réponse finale être total_sum-dp[N] [total_sum / 2]. Regardez le code ci-dessous pour effacer compréhension.

#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;
}
0
répondu palle sai krishna 2015-08-25 12:18:02

Cela peut être résolu en utilisant BST.
Triez d'abord le tableau par exemple arr1
Pour commencer, créez un autre arr2 avec le dernier élément de arr1 (supprimez cet élément de arr1)

Maintenant: répétez les étapes jusqu'à ce qu'aucun échange ne se produise.

  1. Vérifiez arr1 pour un élément qui peut être déplacé vers arr2 en utilisant BST de sorte que le diff soit moins min diff trouvé jusqu'à maintenant.
  2. si nous trouvons un élément, déplacez cet élément vers arr2 et revenez à l'étape 1.
  3. si nous ne trouvons aucun élément dans les étapes ci-dessus, procédez aux étapes 1 et 2 pour arr2 et arr1. c'est-à-dire maintenant vérifier si nous avons un élément dans arr2 qui peut être déplacé vers arr1
  4. continuez les étapes 1 à 4 jusqu'à ce que nous n'ayons pas besoin d'échange..
  5. nous obtenons la solution.

Exemple De Code 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);
    }
}
0
répondu Shaikh Jamir 2016-01-29 03:28:23
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;

}

Appelez la fonction avec SumI = 0 et SumE= sumof tous les éléments dans un. Ce O (n!) la solution calcule la façon dont nous pouvons diviser le tableau donné en 2 parties telle que la différence est minimale. Mais certainement pas pratique en raison de la n! complexité du temps cherchant à améliorer cela en utilisant DP.

-1
répondu Hariprasadmce 2014-03-15 12:40:51

Veuillez vérifier cette logique que j'ai écrite pour ce problème. Cela a fonctionné pour quelques scénarios que j'ai vérifiés. Veuillez commenter la solution, Approche:

  1. Triez le tableau principal et divisez-le en 2 équipes.
  2. commencez ensuite à rendre l'équipe égale en décalant et en échangeant des éléments d'un tableau à l'autre, en fonction des conditions mentionnées dans le code.

Si la différence est la différence de Somme est inférieure au nombre minimum du plus grand tableau (tableau avec plus grande somme), puis déplacez les éléments du plus grand tableau vers un plus petit tableau. le décalage se produit avec la condition, cet élément du plus grand tableau avec une valeur inférieure ou égale à la différence.Lorsque tous les éléments du plus grand tableau sont supérieurs à la différence, le décalage s'arrête et l'échange se produit. Je suis juste en train d'échanger les derniers éléments du tableau (il peut être rendu plus efficace en trouvant les deux éléments à échanger), mais cela a quand même fonctionné. Permettez-moi de savoir si cette logique échoué dans n'importe quel scénario.

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;
}

}

-1
répondu Mohammed Muzzamil 2015-06-13 11:50:21

Une solution possible ici- https://stackoverflow.com/a/31228461/4955513 Ce programme Java semble résoudre ce problème, à condition qu'une condition soit remplie - qu'il y ait une seule et unique solution au problème.

-1
répondu shanti 2017-05-23 11:46:08
#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;
}
-1
répondu Satyajit Tourani 2015-08-25 12:11:49

De nombreuses réponses ont mentionné l'obtention d'une solution "approximative" dans un délai très acceptable . Mais comme il est demandé dans une interview, Je ne m'attends pas à ce qu'ils aient besoin d'un algorithme d'approximation. Aussi, je ne m'attends pas non plus à ce qu'ils aient besoin d'un algorithme exponentiel naïf.

Venir au problème, en supposant que la valeur maximale de la somme des nombres est connue, il peut en fait être résolu en temps polynomial en utilisant la programmation dynamique. Reportez-vous à cette lien https://people.cs.clemson.edu / ~ bcdean / dp_practice / dp_4. swf

-1
répondu MysticForce 2016-08-20 12:09:32
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***
-2
répondu user2522784 2015-09-21 10:18:35