2

たとえば、List にカスタム オブジェクトのコレクションがあるとします。各オブジェクトには、数分 (10 分、15 分、45 分など) に設定された期間プロパティがあります。

それらを 3 時間のリストにグループ化する必要があります。つまり、ListA には、Duration の合計が 3 時間などに等しいオブジェクトのコレクションが含まれます。しかし、最終的なリストは 3 時間に固執する必要があります/そうである必要はありません (つまり、それより短いか等しい可能性があります)。

リストからオブジェクトを読み取り、3 時間の合計期間に基づいて新しいリストを作成するには、どのアルゴリズムを使用する必要がありますか。

ここでの難しさは、30 分のオブジェクトを 5 つと 45 分のオブジェクトを 2 つ持っているとしましょう。ListA で、読んだときに 30 分のオブジェクトを 5 つ追加した場合 (6*50 = 150)、45 分のオブジェクトを 1 つ追加できません。それは3時間に等しくないからです。最初に 45 分のオブジェクトのうち 2 つを追加し、次に 30 分のオブジェクトのうち 3 つ (2*45 + 3*30 = 3 時間) を追加し、他の 2 つのオブジェクトを別のリストに入れます。

読んでくれてありがとう。

4

1 に答える 1

1

最初に大きなオブジェクトを保存し、小さなオブジェクトで完了すると簡単です.

ここに私があなたのために作った簡単なコードがあります、そしてそれはうまくいきます：

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

例では、Int32 オブジェクトを使用してコンソールにありますが、複雑なオブジェクトでも同じです。

すべてのことは、オブジェクトのリストを大きいものから小さいものへと読み取り、それを格納できる最初のストア リストを見つけることです。

結果は次のとおりです。

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

編集： 180のリストと同じくらい必要な場合、これはプロセスとビューの間に追加できる（迅速でミスのある）コードです：

        // 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()));

このコードには満足していませんが、機能しているようです

新しい結果:

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
于 2013-03-20T10:50:30.880 に答える