以下面的例子为例：
1,2,4,1,1
不同的子序列总和可以达到4.例如1,2 2,1.如果存在多个这样的序列,则应该返回相应索引数组的第一个字典：如果有可能找到第一个元素的序列,则必须返回该序列,如果不是,则返回第二个元素.所以一个(迭代(接下一个)和递归(在选择第一个之后,下一个但第一个也应该最接近序列的头部).
因此,对于此示例,我们选择1,1.现在剩下2,1了.如果我们重复这个问题,我们就不能与2匹配：2,4大于4,1小于4.因此我们选择4.最后我们必须选择2和1.
这个概念的实际应用是过山车的队列.你需要4个人才能搭车,但是有些人和他们的朋友在一起,并希望所有人一起乘车.
在这个例子中,1是在线前面的一个人,2是在他身后的一组2个朋友.现在我们总共需要4个人才能完成这次旅行,我们已经有3人,所以我们切断了线路(2和4),然后选择了第一个单人,共计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]的索引数组是不可能的.
