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

1,2,4,1,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,1},4);
groupSum(new int[] {1,3,2},3},4);

它导致：

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

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

背景

这是一种动态编程方法.你生成一个存储器 – 存储 – 为每个总和 – 存储迄今为止最好的解决方案.最初我们没有看到任何值,所以所有项目都包含null,除了包含空arraylist的memory [0](因为零元素的总和为0).所以内存看起来像：

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

现在算法迭代了值.我们遇到的示例案例的第一个值是1.现在我们查找已定义的列表,唯一的一个是memory [0]我们可以将该列表升级为list [0](数组存储索引),其总和结果为1.由于此时该列表的值为null,因此无法替代,因此我们将此列表添加到内存[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,2].第一个问题是[0,2]之和为5,高于和.这不是很有趣,所以我们放弃那个.但问题是,某些地方已包含已列出的内容：

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

对于冲突列表,我们需要寻找解决方案.在这种情况下,比较器 – 在这种情况下LexComp解决了错误.由于我们按字典顺序执行此操作,[0,1]从[2]中的[0,2]和[1]获胜.解决后,列表看起来像：

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,4]
3 -> [0,1] <> [1,4]
2 -> [1] <> [0,4]
1 -> [0] <> [4]
0 -> []

现在,如果我们运行字典比较器,它有时会接受新列表,有时还会接受旧列表.解析后,内存看起来像：

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

现在,我们目前用于生成总计最多为4的组的最佳解决方案已从[3]更改为[0,4].最后,最后一个元素1对游戏的改变不会太大：

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

解决后的内容如下：

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

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

不同的顺序

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