2

可以说，我在 List 中有自定义对象的集合。每个对象的持续时间属性设置为几分钟（10 分钟或 15 分钟或 45 分钟等）

我必须将它们分组在 3 小时的列表中。也就是说，ListA 将收集 Duration 总和应等于 3 小时的对象，依此类推。但最终清单需要/不需要坚持 3 小时（可能更少或相等）

我应该使用哪种算法从列表中读取对象并根据 3 小时的总持续时间创建新列表。

这里的困难可能是，假设我有 5 个 30 分钟的对象和 2 个 45 分钟的对象。在 ListA 中，如果我在阅读时添加了 5 个 30 分钟的对象（6*50 = 150），但我无法添加 1 个 45 分钟的对象。因为那不等于 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 处列出尽可能多的列表，这是一个（快速且方便的）代码，您可以在 process 和 view 之间添加：

        // 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 回答