有人能帮忙提供可能的动态规划算法吗？

Question

首先，我要为即将提出的问题的粗鲁方式道歉。我被另一个网站的成员介绍到这里来，他告诉我我正在寻找一种动态规划算法......我的问题如下。

我正在尝试整理一些数据，并需要在数字中找到可能的顺序。 两组数据都包含以不同顺序列出的相同数字，如下例所示。

54 47 33 58 46 38 48 37 56 52 61 25 ………………第一组
54 52 33 61 38 58 37 25 48 56 47 46 ………………第二组

在这个例子中，从左到右读取数字54、52、61和25在两组中以相同的顺序出现。
因此，其他可能的解决方案是......

54 52 61 25
54 33 58 46
54 33 46
54 33 38 48 56
54 48 56….等等。

虽然这可以手动完成，但我有大量的数据要处理，而且我经常犯错误。 有没有人知道一个现有的程序或脚本，可以输出所有可能的解决方案？

我了解c++和虚拟基础程序的基本结构，并应该能够在任何一个中拼凑出一些东西，但说实话，自ZX Spectrum时代以来，我没有进行过任何严肃的编程，所以请对我宽容一些。然而，我的主要问题不是程序语言本身，而是由于某种原因，我发现无法将完成此任务所需的步骤记录在英语中，更不用说其他任何语言了。

Darcy

- Darcy

---

您是在寻找绝对所有可能的解决方案，还是在寻找最大长度的所有解决方案（如果存在多个这样的实例）？换句话说，像{54}:{54}这样的两个长度为1的集合的解决方案1是否可接受？ - Alexei Polkhanov

嗨Alexei，我正在寻找所有可能的解决方案，从最少2个整数的长度一直到最大长度，包括多个相同长度的解决方案，但解决方案只能包含一个集合中的数字，因为另一个集合仅用于比较...希望这有意义。Darcy - Darcy

Answer 1

听起来您正在寻找“所有常见子序列（ACS）”，这是（更为常见的）最长公共子序列问题（LCS） 的衍生问题。

这里有一篇讨论ACS的论文（虽然他们只关注计算子序列的数量而不是枚举子序列）。

为了设计算法，您应该更明确地定义所需的输出。 为了举例说明，假设您想要一组不包含在任何更长子序列中的子序列。 那么一种算法如下：

1）应用LCS的DP算法，生成对齐/回溯矩阵

2）回溯所有可能的LCS，标记已访问的对齐位置。

3）选择尚未标记的矩阵中的最大元素（剩余最长子序列）

4）回溯，记录序列并标记已访问的对齐位置。

5）当存在未标记的对齐位置时，转到（3）

在您的情况下，回溯很复杂，因为您将不得不访问所有可能的路径（称为“所有最长公共子序列”）。您可以在此处找到LCS的示例实现，这可能有助于您入门。

- academicRobot

---

哇，(A.C.S) 謝謝，這正是我正在尋找的信息。然而，我不確定如何更精確地定義所需的輸出，因為輸出將包括從兩個整數解到最大解的所有內容，並且必須包括相同長度的多個可能解。此外，它還必須能夠處理各種未確定長度的輸入字符串。 顯然，我還有很多閱讀和學習要做。 謝謝 Darcy - Darcy

很高兴能够帮忙。关于定义输出，您的描述指向常见子序列，但我并不完全相信。如果您发现ACS是您想要的，那么这就很好地定义了您的输出。祝你好运。 - academicRobot

Answer 2

我写了这段代码，它输出最长公共序列。虽然它不是特别优化，但时间复杂度为O(n*m)，其中n->数组1的大小，m->数组2的大小：

private void start() {
    int []a = {54, 47, 33, 58, 46, 38, 48, 37, 56, 52, 61, 25};
    int []b = {54, 52, 33, 61, 38, 58, 37, 25, 48, 56, 47, 46};

    System.out.println(search(a,b));
}

private String search(int[] a, int[] b)
{
    return search(a, b, 0, 0).toString();       
}

private Vector<Integer> search(int[] a, int[] b, int s1, int s2) {

    Vector<Vector<Integer>> v = new Vector<Vector<Integer>>(); 

    for ( int i = s1; i < a.length; i++ )
    {
        int newS2 = find(b, a[i], s2);
        if ( newS2 != -1 )
        {
            Vector<Integer> temp = new Vector<Integer>();
            temp.add(a[i]);
            Vector<Integer> others = search(a, b, i+1, newS2 + 1); 
            for ( int k = 0; k < others.size(); k++)
                temp.add( others.get(k));
            v.add(temp);
        }
    }

    int maxSize = 0;
    Vector<Integer> ret = new Vector<Integer>();
    for ( int i = 0; i < v.size(); i++)
        if ( v.get(i).size() > maxSize )
        {
            maxSize = v.get(i).size(); 
            ret = v.get(i);
        }

    return ret;
}

private int find(int[] b, int elemToFind, int s2) {
    for ( int j = s2; j < b.length; j++)
        if ( b[j] == elemToFind)
            return j;
    return -1;
}

- Abbas

---

谢谢，阅读了academicRobots的帖子后，我发现我正在寻找一个全通用子序列解决方案，而您的代码将是我很好的起点。优化不应该是问题，因为我只需要将其用作独立计算器即可。再次非常感谢您。
达西 - Darcy