C#算法求教

Question

这是个“最长公共子序列”问题：
http://zh.wikipedia.org/wiki/最长公共子序列两个容器的情况可以用动态规划来解决。
但多个容器的一般解法是NP-Hard（白话就是很困难）。如果只是你示例中问题规模，可以用穷举的方式来解决。

Answer 1

看不懂你这是什么规则取出的
不是先把1中的都取出,然后取出2,然后取出3,
而是保持容器的高度尽量相等>?
上层的取完才能取下层的，对于三个容器来说，最上层的是一样的就可以用Tn一次全部取出。
如图示三个容器第一层都是obj1，那么先用T1取出的就是C1-OBJ1、C2-OBJ1、C3-OBJ1。最终要确保全部obj取出，且更换Tn最少

Answer 2

另外,你给出的所谓最优结果,根本没有体现T1,T2啊
只标出了顺序,到底放到哪个容器里了?
Tn与OBJn是对应的 如T1->OBJ1，T2->OBJ2。
列出顺序即可

Answer 3

这是个“最长公共子序列”问题：
http://zh.wikipedia.org/wiki/最长公共子序列两个容器的情况可以用动态规划来解决。
但多个容器的一般解法是NP-Hard（白话就是很困难）。如果只是你示例中问题规模，可以用穷举的方式来解决。
非常感谢你的回复。由于非科班，且急于解决遇到的问题，所以有点伸手党的意思容器可能会有多个。

Answer 4

以下是百度知道的一位大侠给出的算法，但是结果有问题。
class Program
    {
         
        static void Main(string[] args)
        {
            IList<CusObject> c1 = new List<CusObject>();
            IList<CusObject> c2 = new List<CusObject>();
            IList<CusObject> c3 = new List<CusObject>();
 
            c1.Add(new CusObject() { index = 1 });
            c1.Add(new CusObject() { index = 3 });
            c1.Add(new CusObject() { index = 4 });
            c1.Add(new CusObject() { index = 5 });
 
            c2.Add(new CusObject() { index = 1 });
            c2.Add(new CusObject() { index = 4 });
            c2.Add(new CusObject() { index = 3 });
            c2.Add(new CusObject() { index = 4 });
            c2.Add(new CusObject() { index = 6 });
 
            c3.Add(new CusObject() { index = 1 });
            c3.Add(new CusObject() { index = 2 });
            c3.Add(new CusObject() { index = 4 });
            c3.Add(new CusObject() { index = 6 });
            c3.Add(new CusObject() { index = 5 });
            c3.Add(new CusObject() { index = 8 });
 
            ArrayList list = new ArrayList();
            int takeInt = 1;
            while (true)
            {
                if (c1.Count() < 1 && c2.Count() < 1 && c3.Count() < 1) break;
 
                CusObject[] c1Objs =
                takeObjects(c1, takeInt);
                CusObject[] c2Objs =
                takeObjects(c2, takeInt);
                CusObject[] c3Objs =
                takeObjects(c3, takeInt);
                CusObject[] merger = new CusObject[0];
                mergerTo(ref merger, c1Objs);
                mergerTo(ref merger, c2Objs);
                mergerTo(ref merger, c3Objs);
                     
                     
                foreach (CusObject obj in merger)
                    list.Add(obj);
                takeInt++;
            }
 
            //test
            foreach (CusObject obj in list)
            {
                Console.WriteLine(obj.index);
            }
 
 
            Console.Read();
        }
 
        public static void mergerTo(ref CusObject[] OldObjects, CusObject[] mergerObjects)
        {
            if (mergerObjects == null || mergerObjects.Count() < 1) return;
            CusObject[] NewObjects = new CusObject[OldObjects.Length + mergerObjects.Length];
            OldObjects.CopyTo(NewObjects, 0);
            mergerObjects.CopyTo(NewObjects, OldObjects.Length);
            OldObjects = NewObjects;
        }
 
        public static CusObject[] takeObjects(IList<CusObject> c,int index)
        {
            if (c.Count() < 1) return null;
            var objects = c.ToArray().Where(w => w.index == index);
            foreach (var obj in objects)
                c.Remove(obj);
            return objects.ToArray();
        }
    }
 
    public class CusObject
    {
       public int index { get; set; }
    }
 
    public class Container
    {
        public CusObject theObject { get; set; }
    }

Answer 5

非常感谢你的回复。由于非科班，且急于解决遇到的问题，所以有点伸手党的意思容器可能会有多个。没错，如果要精确的最少更换次数，必须使用动态规划的算法，用类似'最长公共子序列"这个经典问题的解法解之。
因为需要考虑到容器内部对象的分布，所以要划分子问题，具体就要靠仔细分析啦。
而贪心算法不考虑内部分布，只考虑最顶层的一排对象即可。如果不要求精确解，可以使用贪心算法：
每次只看n个容器最顶层的对象，匹配相同对象的个数最多的那个（假设是最多有k个相同，k<=n），取对应的模具，把k个都取出。然后再根据最顶层对象，确定是否需要换模具取对象。一直到所有容器为空。

Answer 6

[STAThread]
static void Main()
{
    Stack<string>[] buckets = new Stack<string>[] 
    {
        new Stack<string>(new string[]{"J1", "J3", "J4", "J5"}),
        new Stack<string>(new string[]{"J1", "J4", "J3", "J4", "J6"}),
        new Stack<string>(new string[]{"J1", "J2", "J4", "J6", "J5", "J8"}),
    };
    StringBuilder result = new StringBuilder();
    int i = Solve(buckets, null, result);
    Console.WriteLine("更换次数 = {0}\r\n", i);  
    Console.WriteLine(result.ToString());
}
// 穷举法
static int Solve(Stack<string>[] buckets, string lastCategory, StringBuilder result)
{
    int minCost = int.MaxValue;
    StringBuilder minResult = null;
    for (int i = 0; i < buckets.Length; i++)
    {
        Stack<string> c = buckets[i];
        if (c.Count > 0)
        {
            string s = c.Pop();
            StringBuilder subResult = new StringBuilder((i + 1) + "->" + s  + "\r\n");
            int cost = (s == lastCategory ? 0 : 1) + Solve(buckets, s, subResult);
            if (cost < minCost)
            {
                minCost = cost;
                minResult = subResult;
            }
            c.Push(s);
        }
    }
    if (minCost == int.MaxValue) minCost = 0;
    else result.Insert(0, minResult.ToString());    return minCost;
}

Answer 7

就是这样的，非常感谢！
可否再帮忙做个优化，排出来的结果默认从第一个容器开始，然后后续每次更换Tn时都默认从上一个tn的最后一个容器开始取物体。

Answer 8

这等问题对于你们这样的高手可能只是几行代码的事，对我来说却是困扰许久的难题。
再次向Forty2致敬！

Answer 9

1.三个容器(堆栈)有顺序的,例如,c1->c2->c3->c2->c1(好像是一个双向链表,到链表的顶或者尾就反向遍历)...如此
2.取数算法:第一取一个容器的第一位开始(c1),然后开始参照旁边的容器(顺序是(1)中算法),如果当前的容器上栈顶的编号比旁边的要小于等于,取出来,直到比旁边的栈顶大的,就轮到下一个容器,直到操作完成.