回溯算法 - 试图找到更好的解决方案

Question

我想在我目前正在从事的项目中寻求一些帮助，我应该在这里使用回溯来创建一种“组织程序”。

这个故事是，我有一定数量的动物，每只动物都有自己的类型，栖息地和属性。我还列出了整数列表，其中包括所有可能的笼子大小可以放入。在每个笼子大小中，我可以创建一个无限数量的实际笼子。只要它们的大小小于或等于笼子的大小，就可以将两只（或更多）动物保存在相同的笼子中，并且它们是相同类型的（例如哺乳动物）或共享相同的栖息地（例如土地）。

我的算法应该将它们整理成笼子，以便最后，我得到了一个笼子清单，所有动物都放置了所有动物，并且使用了最少的笼子。

为了说明，假设我们有3只动物，两只猫（哺乳动物，土地，3个）和一个秃鹰（鸟，空气，4），我们可能的笼子大小为3、5、7。显然，只是看着在此示例中，我们可以看到，虽然猫可以在同一笼子中，但秃鹰将不可避免地会自行着陆，因此使用最少的笼子显然是2。猫; 5：秃鹰}或{7：猫，猫; 7：秃鹰}。

我最初通过递归设置回溯算法的方式是：

• n ：动物总数（在上面的示例中，这将是3
• m ：可以用来创建我们的笼子的数字列表（同样，这是三个）
• r ：我正在考虑使用给出的尺寸创建一个空的列表，但是目前我只是直接使用整数
• e ：当前周期的解决方案
• opt ：到目前为止，每当一个周期的e包含的笼子少于opt时，可以保存的最佳场景 新的

。

• 作为
• 检查 可以适合以前的任何一个笼子，因为仍然有足够的空间，并且可以将其与所有其他动物一起放置在同一笼子里

。首先检查它们是否可以自己安装，如果是，它还可以检查是否可以将其放在以前的笼子中。如果不能，它将创建一个新的笼子并添加动物，然后将笼子添加到E中，但是如果可以将其放入先前的笼子中，它将做得很多。

显然，这并不是很好。我向我的TA寻求一些帮助，他建议我考虑以下内容：

• n ：动物数量
• m ：n减去水平，这意味着随着我的移动越来越多在内部，我将无需放置一定数量的动物。因此，例如，在第一级，我仍然需要放置3只动物，而仅在第二层，而最终级别仅1。
• r ：笼子里的动物（？我没有t非常了解他在这里的意思，他的更深入的解释也没有帮助）
• e ：笼子清单，与上述
• f1 相同：检查动物是否可以是放在给定的笼子中，以及它是否可以与
• f2

中 的所有其他动物保持在一起说，我目前无法完全掌握他的解决方案，尽管我的确实在一定程度上有缺陷（例如，它仅检查可以放置动物的第一个可能的笼子，而无需检查所有其他可能性）。 我要在这里复制我的代码，目前看起来像这样，但是老实说，我更多地在寻找（和/或理解）更好的解决方案时寻求帮助。

对不起，这太长了，我可能会过度思考/过度解释这一点，但是在这个阶段我感到非常拼命哈哈。任何帮助将不胜感激！

public virtual void Trial(int level, ref CageList<Cage> E, ref CageList<Cage> OPT, ref bool found)
        {
            int i = -1;

            while (i < M[level]-1)
            {
                i++;
                ListObj<int> R_obj = R.FindIndex(i);


                if (f1(szint, R_obj))
                {
                    int k = 0; 

                    if (E.head == null)
                    {
                        AddFirsttoE(level, R_obj, ref E);
                    }
                    else
                    {
                        while (k < E.Count() && !f2(level, E.FindIndex(k), k, ref E, R_obj))            
                        {
                            k++;
                        }
                    }


                    if (level == N - 1)
                    {
                        if(!found || E.Count() < OPT.Count())
                        {
                            OPT = E;
                        }
                        found = true;
                    }
                    else
                    {
                        Trial(level + 1, ref E, ref OPT, ref found);
                    }
                }
                freeE(level, ref E);
            }
        } 

我的其他两个功能是：

public override bool f1(int level, ListObj<int> obj)
        {

            bool ret = false;
            ListaObj<Animal> test = Animals.FindIndex(level);

            if (((int)test.Content.Size).CompareTo(obj.Content) <= 0)
            {
                ret = true;
            }
            return ret;
        }
public override bool f2(int level, ListObj<Cage> obj, int level2, ref CageList<Cage> E, ListObj<int> empty_size)
        {
            bool ret = false;
            ListObj<Animal> test = Animals.FindIndex(level);
            bool can_keep_together = true;

            if (((int)test.Content.Size).CompareTo(obj.Content.CageSize) <= 0)  
            {
                AnimalList<Animal> caged = obj.Content.Animals;
                ListObj<Animal> p = caged.head;

                while (p != null && can_keep_together)                                   
                {
                    if (!p.Content.CanKeepTogether(test.Content))
                    {
                        can_keep_together = false;
                    }
                    p = p.Next;
                }

                if (can_keep_together)  
                {
                    ret = true;
                    obj.Content.Animals.Add(test.Content);
                    obj.Content.CageSize -= (int)test.Content.Size;
                }
            }
            else if (level2 == E.Count() - 1)  
            {
                ret = true;
                AnimalList<Animal> new_animal_list = new AnimalList<Animal>();
                new_animal_list.Add(test.Content);
                Cage new_cage = new Cage(empty_size.Content, new_animal_list);
                new_cage.CageSize -= (int)test.Content.Méret;
                E.Add(new_cage);
            }

            if (!can_keep_together && level2 == E.Count()-1)
            {
                ret = true;
                AnimalList<Animal> new_animal_list = new AnimalList<Animal>();
                new_animal_list.Add(test.Content);
                Cage new_cage = new Cage(empty_size.Content, new_animal_list);
                new_cage.CageSize -= (int)test.Content.Méret;
                E.Add(new_cage);
            }
            return ret;
        }