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

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

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"

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

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

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

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

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.

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

}

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.

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

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

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***