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

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个人才能搭车,但是有些人和他们的朋友在一起,并希望所有人一起乘车.

在这个例子1中,前面是一个人,2是2他背后的一群朋友.现在我们需要一共4有人来完成这次旅行,我们已经拥有了3,所以我们切断了线路(2和4)并占用了第一个人,这总共给了我们4个人.

Answer 1

如果我正确理解了这个问题，那么您基本上要做的就是对数字进行分组，使总和为 ，4并且优先考虑首先在队列中添加数字。

您可以使用动态编程方法来完成此操作。我在这里使用 aint[]和 an intas sum，但问题可以推广到大多数数据结构。

首先，您必须定义一个比较器来比较索引列表，例如字典索引列表：

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 -> []

现在算法迭代这些值。我们在示例中遇到的第一个值是 a 1。现在我们寻找已经定义的列表，唯一的一个是memory[0]我们可以将该列表升级[0]为一个列表（数组存储索引），其总和结果为1. 由于此时该列表的值null没有其他选择，因此我们将此列表添加到 to 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]5sum

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]or [0,1,4]。

顺序不同

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