diviser un tableau en deux ensembles avec une différence minimale

Question

Une question d'entrevue que j'ai trouvé:

Étant donné un tableau de nombres, de diviser les nombres en deux ensembles tels que l'écart entre la somme des nombres dans deux jeux est le minimum.

C'est l'idée que j'ai, mais je ne suis pas sûre que ce soit une bonne solution:

1. trier le tableau
2. Prendre les 2 premiers éléments..les considérer comme 2 jeux (chacune avec 1 élément)
3. Prendre l'élément suivant du tableau.
4. Maintenant décider de quelle jeu de cet élément (par calcul de la somme..il devrait y avoir un minimum)
5. répétez

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

Answer 1

Le problème que vous décrivez est la partition de problème. Trouver une solution optimale est un problème NP-complet cependant il y a un certain nombre d'approximations qui sont presque parfait pour la plupart des cas.

En fait, l'algorithme que vous avez décrit, c'est la façon aire de jeux enfants cueillir des équipes. Cet algorithme glouton effectue remarquablement bien si les nombres dans l'ensemble sont similaires à des ordres de grandeur. Bien sûr, ce n'est pas la meilleure solution, mais vu comment le problème est NP-complet, c'est assez mince sacrément bon pour sa simplicité.

Cet article Scientifique Américain donne une excellente analyse du problème et que vous devez aller à travers et de le lire: la méthode La plus Simple Problème Difficile.

Answer 2

Non, ça ne marche pas. Il n'y a pas de solution temporelle polynomiale (sauf si P = NP). Le mieux que vous puissiez faire est de simplement regarder tous les différents sous-ensembles ...

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

Considérons la liste [0,1,5,6].

Vous déclarerez {0,5} et {1,6} lorsque la meilleure réponse est réellement {0,1,5} et {6}.

Answer 3

Approche des combinaisons par combinaisons:

 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 4

Un petit changement: inverser l'ordre - commencez par le plus grand nombre et diminuez. Cela minimisera l'erreur.

Answer 5

Êtes-vous en train de trier votre sous-ensemble en ordre décroissant ou en ordre croissant?

Pensez-y comme ceci, le tableau {1, 3, 5, 8, 9, 25}

si vous deviez diviser, vous auriez {1,8,9} = 18 {3,5,25} = 33

Si elle était classée par ordre décroissant, cela fonctionnerait beaucoup mieux

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

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

EDIT: Lire le post de tskuzzy. Le mien ne fonctionne pas