Comment créer une nouvelle liste à partir d'une collection existante en fonction de certains critères ?

Question

Disons que j'ai une collection d'objets personnalisés dans une liste. Chaque objet a une propriété de durée fixée à quelques minutes (10 minutes ou 15 minutes ou 45 minutes, etc.).

Je dois les regrouper en 3 heures de liste. C'est-à-dire que la liste A contiendra une collection d'objets dont la somme des durées sera égale à 3 heures et ainsi de suite. Mais la liste finale doit/n'a pas besoin de correspondre à 3 heures (c'est-à-dire qu'elle peut être inférieure ou égale).

Quel algorithme dois-je utiliser pour lire l'objet de la liste et créer de nouvelles listes sur la base de 3 heures de durée totale.

La difficulté ici pourrait être la suivante : disons que j'ai 5 objets de 30 minutes et 2 objets de 45 minutes. Dans la liste A, si j'ai ajouté 5 objets de 30 minutes (6*50 = 150) comme je l'ai lu, je ne peux pas ajouter 1 objet de 45 minutes. Parce que cela ne sera pas égal à 3 heures. J'aurais donc ajouté 2 objets de 45 minutes en premier et 3 objets de 30 minutes ensuite (2*45 + 3*30 = 3 heures) et laissé les 2 autres objets dans une autre liste.

Merci de votre lecture.

Answer 1

Cela peut être facile si vous essayez de stocker d'abord les gros objets et de compléter avec les plus petits.

Voici un code rapide que j'ai créé pour vous, et qui fonctionne bien :

    static void Main(string[] args)
    {
        // data
        List<Int32> listElement = new List<Int32>() { 10, 20, 10, 30, 45, 10, 20, 30, 40, 50, 60, 40, 30, 50, 60, 70, 80, 90, 20, 30, 10, 50, 60, 40, 60, 80, 90, 60, 80, 70, 80, 90, 90, 50 };
        Int32 MaxStack = 180;

        // result
        List<List<Int32>> listResult = new List<List<Int32>>();

        // process
        foreach (Int32 element in listElement.OrderByDescending(i => i))
        {
            List<Int32> listToStore = listResult.Where(l => l.Sum() + element <= MaxStack).FirstOrDefault();
            if (listToStore == null)
            {
                listToStore = new List<Int32>();
                listResult.Add(listToStore);
            }

            listToStore.Add(element);
        }

        // view
        foreach (List<Int32> list in listResult)
        {
            Console.Write("List " + (listResult.IndexOf(list) + 1) + "[total " + list.Sum() + "]: ");                
            foreach (Int32 element in list)
            {
                Console.Write(element.ToString() + " ");
            }

            Console.WriteLine();
        }

        Console.ReadKey();
    }

Pour l'exemple, c'est en console, avec l'objet Int32, mais c'est la même chose pour les objets complexes.

Il suffit de lire votre liste d'objets du plus grand au plus petit, et de trouver la première liste de magasin qui peut le stocker.

Le résultat est :

List 1[total 180]: 90 90
List 2[total 180]: 90 90
List 3[total 180]: 80 80 20
List 4[total 180]: 80 80 20
List 5[total 180]: 70 70 40
List 6[total 180]: 60 60 60
List 7[total 180]: 60 60 50 10
List 8[total 180]: 50 50 50 30
List 9[total 175]: 45 40 40 30 20
List 10[total 90]: 30 30 10 10 10

Edit : Si vous voulez autant que la liste à 180, c'est un code (rapide et facile) que vous pouvez ajouter entre le processus et la vue :

        // switching element for better fill
        List<List<Int32>> unfilledlist = listResult.Where(l => l.Sum() < MaxStack).ToList();
        // truncate original result
        unfilledlist.ForEach(l => listResult.Remove(l));

        while (unfilledlist != null && unfilledlist.Count > 1)
        {
            List<Int32> list = unfilledlist.First();
            unfilledlist.Remove(list);

            foreach (Int32 element in list)
            {
                Int32 needed = MaxStack - list.Sum() + element;
                Boolean isFound = false;

                foreach (List<Int32> smallerlist in unfilledlist)
                {
                    List<Int32> switchingList = new List<int>();

                    // searching how to fill what we needed
                    foreach (Int32 e in smallerlist.OrderByDescending(i => i))
                    {
                        if (e + switchingList.Sum() <= needed)
                            switchingList.Add(e);
                    }

                    // we found a possible switch
                    if (switchingList.Sum() == needed)
                    {
                        // moving first element
                        list.Remove(element);
                        smallerlist.Add(element);

                        // moving element
                        switchingList.ForEach(e => { smallerlist.Remove(e); list.Add(e); });
                        isFound = true;
                        break;
                    }
                }

                if (isFound)
                    break;
            }

            listResult.Add(list.OrderByDescending(i => i).ToList());
        }

        // completing result with lists that are not with sum 180
        unfilledlist.ForEach(l => listResult.Add(l.OrderByDescending(i => i).ToList()));

Je ne suis pas satisfait de ce code, mais il semble fonctionner

Nouveau résultat :

List 1[total 180]: 90 90
List 2[total 180]: 90 90
List 3[total 180]: 80 80 20
List 4[total 180]: 80 80 20
List 5[total 180]: 70 70 40
List 6[total 180]: 60 60 60
List 7[total 180]: 60 60 50 10
List 8[total 180]: 50 50 50 30
List 9[total 180]: 40 40 30 30 20 10 10
List 10[total 85]: 45 30 10