java - 对序列进行分组是具有给定总和的子序列，并具有字典序优先级

Question

我正在寻找一种方法来搜索给定序列中的子序列，该子序列总和为给定数字( sum ，此处为 4 )并具有字典序优先级。

以下面的例子为例:

1,2,2,4,1,1

不同的子序列可以相加为4 .例如 1,2,1 , 2,2 2,1,1 .如果存在多个这样的序列，则应返回相应索引数组的按字典顺序排列的第一个:因此，如果可以找到具有第一个元素的此类序列，则必须返回该序列，如果没有，则瞄准第二个和所以一个(迭代(采用下一个)和递归(在选择第一个之后，下一个但第一个也应该最接近序列的头部)。

所以对于这个例子，我们选择 1,2,1 .现在 2,4,1离开了。如果我们重复这个问题，我们将无法与 2 匹配。 :2,4大于 4和 2,1小于 4 .因此我们选择 4 .最后我们必须选择2和 1 .

这个概念的一个实际应用是过山车的队列。您需要 4 人乘坐，但有些人与他们的 friend 成群结队，并希望所有人一起乘坐同一趟车。

在这个例子中 1排在最前面的是一个人，2是一群2他身后的 friend 。现在我们总共需要4这趟旅程的人，我们已经有了 3 ，所以我们切线( 2 和 4 )并选择第一个单例，这样我们总共有 4 个人。

Answer 1

如果我正确理解了问题，那么您基本上要做的是将数字分组，使总和为 4并且您优先在队列中添加号码。

您可以使用动态编程方法来做到这一点。我在这里使用 int[]和一个 int总而言之，但该问题可以推广到大多数数据结构。

首先，您必须定义一个比较器来比较 的列表。指数 例如一个字典:

public class LexComp<T extends Comparable<T>> implements Comparator<List<T>> {

    @Override
    public int compare (List<T> la, List<T> lb) {
        Iterator<T> ita = la.iterator();
        Iterator<T> itb = lb.iterator();
        while(ita.hasNext() && itb.hasNext()) {
            T ea = ita.next();
            T eb = itb.next();
            int cr = ea.compareTo(eb);
            if(cr != 0x00) {
                return cr;
            }
        }
        if(itb.hasNext()) {
            return 1;
        } else if(ita.hasNext()) {
            return -1;
        }
        return 0;
    }

}

接下来您可以使用以下方法:

public ArrayList<Integer> groupSum (int[] values, int sum) {
    ArrayList[] memory = new ArrayList[sum+1];
    memory[0] = new ArrayList<Integer>();
    LexComp<Integer> lc = new LexComp<Integer>();
    int index = 0;
    for(int val : values) {
        for(int i = sum-val; i >= 0 ; i--) {
            if(memory[i] != null) {
                ArrayList<Integer> tmp = (ArrayList<Integer>) memory[i].clone();
                tmp.add(index);
                if(memory[i+val] == null || lc.compare(tmp,(ArrayList<Integer>) memory[i+val]) < 0) {
                    memory[i+val] = tmp;
                }
            }
        }
        index++;
    }
    return memory[sum];
}

此方法返回 ArrayList<Integer>的 指数 其对应元素的总和为 sum和 null如果不能创建这样的组。它将根据LexComp 优先考虑某些组比较器。

对于您给定的输入:

groupSum(new int[] {1,2,2,4,1,1},4);
groupSum(new int[] {1,2,3,2,2,2},4);
groupSum(new int[] {1,2,2,3},4);
groupSum(new int[] {1,2,2,3,1},4);

结果是:

[0, 1, 4]
[0, 2]
[0, 3]
[0, 1, 4]

所以你应该选择第一个、第二个和第五个元素，它们确实总和为 4 .然后，您必须自己从阵列中删除这些项目并重新运行该过程。如果不能构造这样的总和，或者没有足够的元素来求和 4 - 如前所述 - 算法将返回 null .在这种情况下，您必须发明一种回退机制。也许返回组与sum 的差别最小。 .

背景

这是一种动态规划方法。您生成一个 memory其中存储 - 对于每个总和 - 迄今为止找到的最佳解决方案。最初我们没有看到任何值，所以所有项目都包含 null除了 memory[0]它包含一个空的数组列表(因为零元素的总和是 0 )。所以内存看起来像:

Mem
4 -> null
3 -> null
2 -> null
1 -> null
0 -> []

现在算法迭代这些值。我们在示例案例中遇到的第一个值是 1 .现在我们寻找已经定义好的列表，唯一的就是 memory[0]我们可以将该列表升级为列表 [0] (数组存储索引)其总和结果为 1 .从那时起，该列表的值为 null没有其他选择，因此我们将此列表添加到 memory[1] :

Mem
4 -> null
3 -> null
2 -> null
1 -> [0]
0 -> []

下一项是 2 : 我们可以升级两个列表 [] -> [1]和 [0] -> [1]这些将导致带有总和的列表 2和 3分别，所以我们将它们存储在内存的这些索引中:

Mem
4 -> null
3 -> [0,1]
2 -> [1]
1 -> [0]
0 -> []

下一项再次是 2 .现在我们可以升级 4列表:[] -> [2] , [0] -> [0,2] , [1] -> [1,2]和 [0,1] -> [0,1,2] .第一个问题是[0,1,2]的总和是 5高于 sum .这并不有趣，所以我们放弃了那个。然而，问题是，有些地方已经包含了列表:

Mem
4 -> null
3 -> [0,1] <> [0,2]
2 -> [1] <> [2]
1 -> [0]
0 -> []

对于冲突的列表，我们需要寻找解决方案。在那种情况下比较器 - 在这种情况下是 LexComp解决错误。由于我们按字典顺序执行此操作，[0,1]来自 [0,2] 的胜利和 [1]来自 [2] .解析后，列表如下所示:

Mem
4 -> [3]
3 -> [0,1]
2 -> [1]
1 -> [0]
0 -> []

下一个元素是 4 .我们可以升级的唯一列表使得总和仍然小于或等于 sum是 [] -> [3]

Mem
4 -> [3]
3 -> [0,1]
2 -> [1]
1 -> [0]
0 -> []

下一个元素是 1 .我们可以升级除一个列表之外的所有列表 4 -> [3] (否则总和将大于 4 )。但这又导致了很多冲突:

Mem
4 -> [3] <> [0,1,4]
3 -> [0,1] <> [1,4]
2 -> [1] <> [0,4]
1 -> [0] <> [4]
0 -> []

现在，如果我们运行按字典序排列的比较器，它有时会接受新列表，有时会接受旧列表。解析后，内存如下:

Mem
4 -> [0,1,4]
3 -> [0,1]
2 -> [0,4]
1 -> [0]
0 -> []

现在，我们当前生成总和为 4 的组的最佳解决方案已从 [3] 更改为至 [0,1,4] .最后一个元素 1不会对游戏有太大改变:

Mem
4 -> [0,1,4] <> [0,1,5]
3 -> [0,1] <> [0,4,5]
2 -> [0,4] <> [0,5]
1 -> [0] <> [5]
0 -> []

决议后的内容如下:

Mem
4 -> [0,1,4]
3 -> [0,1]
2 -> [0,4]
1 -> [0]
0 -> []

现在我们已经考虑了所有元素和生成 4 的最佳解决方案。是 memory[4]或 [0,1,4] .

不同的顺序

这种方法可以概括为提供不同的 Comparator在 List<T> (这里是 LexComp<T> )将优先考虑另一个索引数组。比较器应始终至少满足传递性约束:如果 x 小于 y 且 y 小于 z:x 必须小于 z。此外，索引列表将始终增加。 [4,1,0] 的索引数组因此是不可能的。