Division d'une liste de valeurs en trois sous-totaux égaux

Question

J'ai une liste de nombres qui totalisent 540000. Je voudrais trier cette liste en 3 listes dont chacune total 180000. Quelle est la méthode de programmation la plus efficace pour ce faire, en supposant que la liste des nombres est un fichier plat avec un nombre par ligne?

Answer 1

Cela ressemble à une variante du Knapsack problem. Il serait utile de connaître la taille de ces chiffres, et comptez - y a-t-il d'énormes variations de taille ou sont-elles toutes semblables? Y en at-il beaucoup (> 1000) ou seulement quelques-unes (< 100)? Une méthode simple et rapide serait de les trier dans l'ordre de taille - le plus grand au plus petit - puis bouclez-les, en plaçant le premier dans la première liste, le deuxième dans la deuxième liste, le troisième dans la troisième liste, et puis revenez et mettez le quatrième dans la première liste ... et ainsi de suite. Peut fonctionner assez bien pour beaucoup de petits nombres ... mais il existe d'autres approches pour différents types de données.

Answer 2

for i as integer = 1 to 180000 
put data in array 1 
next i 

for i as integer = 180001 to 360000 
put data in array 2 
next i 

for i as integer = 360001 to 540000 
put data in array 3 
next i 

Answer 3

Cela a l'odeur de NP-hardness pour moi - dans ce cas, il n'y a pas de façon «efficace» de le faire. Bien que vous pourriez probablement trouver un certain nombre d'heuristiques qui pourraient l'aborder plutôt bien.

Cela dit que vous avez toujours des problèmes avec des listes comme [179998, 180001, 180001] :)

Answer 4

J'ai écrit un code Java pour faire la plupart du travail pour vous.

La plus petite des méthodes prend une liste de nombres et un total à atteindre, et renvoie un ensemble de listes de nombres qui s'ajoutent à ce total. Vous pouvez le faire avec 18000 et votre liste de numéros.

Pour chaque liste de nombres renvoyés, vous devez créer une nouvelle liste qui ne contient pas les nombres déjà utilisés, et exécuter la méthode sur 18000 et encore.

Si cette deuxième appel retourne une ou plusieurs listes, vous saurez le problème est soluble, car le nombre restant également ajouter jusqu'à 18000.

Quoi qu'il en soit, voici le code. Oui, c'est juste de la force brute récursive. Il est très probable qu'il n'y a aucune méthode éprouvée pour faire toujours mieux par une autre méthode. Ne me blâmez pas si ça dure longtemps; vous voudrez peut-être essayer avec des exemples plus petits en premier.

import java.util.*; 

public class Listen { 

    private static Set<List<Integer>> makeFrom(int total, List<Integer> numbers) { 
     Set<List<Integer>> results = new HashSet<List<Integer>>(); 
     List<Integer> soFar = new ArrayList<Integer>(); 
     makeFrom(results, total, soFar, numbers, 0); 
     return results; 
    } 

    private static void makeFrom(Set<List<Integer>> results, int total, List<Integer> soFar, List<Integer> numbers, int startingAt) { 
     if (startingAt >= numbers.size()) return; 
     for (int p=startingAt; p<numbers.size(); p++) { 
     Integer number = numbers.get(p); 
     List<Integer> newSoFar = new ArrayList<Integer>(soFar); 
     newSoFar.add(number); 
     int newTotal = total - number; 
     if (newTotal < 0) continue; 
     if (newTotal == 0) { 
      Collections.sort(newSoFar); 
      results.add(newSoFar); 
     } else { 
      List<Integer> newNumbers = new ArrayList<Integer>(numbers); 
      newNumbers.remove(number); 
      makeFrom(results, newTotal, newSoFar, newNumbers, startingAt + 1); 
     } 
     } 
    } 

    public static void main(String[] args) { 
     List<Integer> numbers = new ArrayList<Integer>(); 
     for (int j=1; j<11; j++) numbers.add(j); 
     for (List<Integer> result : makeFrom(25, numbers)) { 
     System.out.println(Arrays.deepToString(result.toArray(new Integer[result.size()]))); 
     } 
    } 
} 

Answer 5

Comme ian-Witz déjà fait remarquer, cela est probablement un problème du type NP-complet: Cela signifie qu'il n'y a pas de solution vraiment bon pour le cas général, à court d'essayer toutes les possibilités. Les algorithmes qui font cela ont tendance à devenir spectaculairement lent à mesure que la quantité de données qu'ils traitent augmente.

Cela dit, voici mon algorithme pour former des sous-listes ayant une certaine somme d'une liste donnée d'entiers:

Set up a place to hold your results. The results will all be lists of numbers, each some sub-set of your original list. We don't know how many such lists will result; possibly none. 

Put your list of numbers into an array so you can refer to them and access them by index. In the following, I'm assuming array indices starting at 1. Say you have 10 numbers, so you put them into a 10 element array, indexed by positions 1 through 10. 

For performance reasons, it may help to sort your array in descending order. It's not necessary though. 

Run a first index, call it i, through this array, i.e. through index values 1 through 10. 
For each index value: 
    select the number at index position i, call it n1. 
    set up a new list of numbers, where we will be assembling a sub-list. call it sublist. 
    add n1 to the (so far empty) sublist. 
    If i is already at 10, there's nothing more we can do. Otherwise, 
    Run a second index, call it j, through the arrray, starting at i+1 and going up to 10. 
    For each value of j: 
    select the number at index position j, call it n2. 
    add n2 to the sublist containing n1 
    calculate the sum of our sublist so far: Does it add up to 18000? 
    If the exact total is reached, add the current sublist to our result list. 
    If the total is exceeded, there's nothing we can add to make it better, so skip to the next value of j. 
    If the total is less than 18000, you need to pick a third number. 
    Run a third index, call it k, through the array, starting at j+1 and going up to 10. Skip this if j is already at 10 and there's no place to go. 
    For each value of k: 
     select the number at k, call it n3 
     add n3 to the sublist 
     check the sublist total against the expected total 
     if the exact total is reached, store the sublist as a result; 
     if it's less than the expected, start a 4th loop, and so on. 

     When you're done with checking a value for a loop, e.g. n4, you need to take your latest n4, n3 or whatever back out of the sublist because you'll be trying a different number next. 

    Whenever you find a combination of numbers with the correct sum, store it in your results set. 

When you've run all your loop counters into the wall (i.e. i is 10 and there's nowhere left to go), your "results" set will contain all sub-lists of the original list that added up to the desired total. It's possible there will be none, in that case there's no (exact) solution to your problem. 

If you have 3 or more sub-lists in your results set, you can check if you can find a pair of them that use non-overlapping sets of numbers from the original list. If you have 2, then there should also be a 3rd sub-list containing exactly all the numbers not contained in the first 2 lists, and you have your solution. 

Mon code exemple ne fait pas une série de boucles; au lieu de cela, il fait une boucle allant de 1 à (disons) 10 et cherchant 18000. Ensuite, disons que le premier nombre choisi était 2000, la fonction s'appelle de nouveau récursivement avec un indice pour commencer à 2 (= i + 1) et pour essayer d'assembler un total de 16000. Cet appel de la fonction s'appelle alors encore avec une position de départ de (quel que soit 1) et un total de (16000 - peu importe), et il continue à s'appeler ainsi avec des sous-ensembles de l'original problème jusqu'à ce qu'il n'y ait plus de place pour les index à monter. S'il trouve une "bonne" sous-liste en chemin, elle la stocke dans le jeu de résultats.Comment implémenter cela efficacement dépend de la langue dans laquelle vous le faites. FORTRAN 77 n'a pas de récursivité, Lua n'implémente pas les listes ou les ensembles efficacement, Lisp peut avoir des problèmes d'indexation efficace dans une liste. En Java, je pourrais utiliser un bitet plutôt qu'une sous-liste. Je ne sais rien sur P4GL, donc: Pour la mise en œuvre, vous êtes seul!