对序列进行分组是具有给定总和且具有字典序优先级的子序列
Grouping a squence is subsequences with a given sum with lexicographical priority
我正在寻找一种方法来搜索给定序列中总和为给定数字（sum，此处为 4）且具有字典优先级的子序列。
以下面的例子为例：
1,2,2,4,1,1
不同的子序列可以加起来4。例如1,2,1、2,22,1,1。如果存在多个这样的序列，则应返回相应索引数组的字典序第一个：因此，如果可以用第一个元素找到这样的序列，则必须返回那个，否则，瞄准第二个和所以一个（迭代（取下一个）和递归（在第一个 select 之后，下一个但第一个也应该最接近序列的头部）。
所以对于这个例子，我们 select 1,2,1。现在还剩2,4,1。如果我们重复这个问题，我们就无法与 2 匹配：2,4 大于 4 并且 2,1 小于 4。因此我们 select 4。最后我们要select2和1.
这个概念的一个实际应用是过山车的队列。您需要 4 个人乘坐，但有些人和他们的朋友成群结队，希望所有人一起乘坐同一趟车。
在这个例子中1是排在最前面的一个人，2是他后面的一群2朋友。现在我们这次骑行总共需要 4 人，而我们已经有 3，所以我们插队（2 和 4）并带上第一个人，这给了我们总共 4 个人。
您可以遍历列表并按顺序添加，直到它大于您要查找的值。
代码：
public static int addListValues(int[] list, int num){//Returns number which can not be added by anything else in the list to be <= num.
boolean b[] = new boolean[list.length];//List of numbers already taken care of. True for not, false for cleared.
for(int i = 0; i < b.length; i++){
b[i] = true;
}
int count = 0;//Amount of numbers in int[] list which have been added to equal less than or equal to num.
int total = 0;
while(true){//loops until values left can not be added to equal or be less than num.
int check = 0;
for(int i = 0; i < list.length; i++){//Loops through list.
if(b[i]){//If the number has not been added already.
System.out.println("CHECKING: " + i);
if(total + list[i] > num){//Adds to check if the number is greater than num.
check++;
}
if(total + list[i] <= num){//Adds numbers together to equal num or less than num.
System.out.println("TEST: " + list[i] + " TOTAL: " + total);
if(total + list[i] != num){
boolean contains = false;
int index = 0;
for(int o = 0; o < list.length; o++){
if(list[o] == num - total && b[o] && o != i){
contains = true;
index = o;
break;
}
}
if(contains){
System.out.println("1: " + index + ", " + list[index]);
b[index] = false;
count++;
total = 0;
}else{
System.out.println("2");
b[i] = false;
count++;
total+= list[i];
}
}else{
System.out.println("3");
b[i] = false;
count++;
total = 0;
}
}else if(check == list.length - count){//Check if "check" is equal to the amount left over. In other words, if the numbers left are higher than the number you are looking for.
System.out.println("FINAL: 3");
int t = 0;
for(int j = 0; j < list.length; j++){
if(b[j]){
t += list[j];
}
}
return t;//More than one number is left and is higher than num. Returns numbers left added together
}else if(count == list.length-1){
System.out.println("FINAL: 2");
return list[i];//returns list[i] if it is the only number left over.
}
}else if(count >= list.length){
System.out.println("FINAL: 1");
return total;//Returns total if there is nothing left over. The total may be anything less than the "num".
}
}
}
}
我已经用多组数字测试了这个方法并且有效。如果遗留的值超过 4 个，我不确定 return 该怎么办，所以我添加了遗留的值并 return 编辑了这个。
此代码不需要任何导入。
这个问题的正确答案在很大程度上取决于您如何定义优先级。
如果可能，我们应该总是选择队伍中的第一组，还是让尽可能多的人排在队伍前面是最佳解决方案？
即给出
1, 2, 2, 3, 3, 4, 2, 2, 3, 1
是最优解
1, 2, 1
或
1、3
为了让您开始，这里有一个执行第一个的递归解决方案：
private static List<Integer> getSumIndices(int sum, List<Integer> queue) {
return getSumIndices(sum, new ArrayList<>(queue), 0);
}
private static List<Integer> getSumIndices(int sum, List<Integer> queue, int offset) {
System.out.printf("Looking for sum %s in values of %s with offset %s%n", sum, queue, offset);
if(sum == 0) {
//Base case
return new ArrayList<>();
}
for(int i = 0; i < queue.size(); i++) {
int value = queue.get(i);
// Can we actually use this group
if(value <= sum) {
try {
// See if we can find the remainder if we use this group
ArrayList<Integer> list = new ArrayList<>();
list.add(i + offset);
list.addAll(getSumIndices(sum - value, queue.subList(i + 1, queue.size()), offset + i + 1));
return list;
} catch(IllegalArgumentException e) {
// We couldn 't, continue looking
}
}
}
// We could not construct the sum using the values in the queue
System.out.printf("Failed to construct sum %s from values in %s%n", sum, queue);
throw new IllegalArgumentException(String.format("Could not construct sum %s from values in %s%n", sum, queue));
}
结果：
q=[1, 2, 2, 3, 3, 4, 2, 2, 3, 1]
Looking for sum 4 in values of [1, 2, 2, 3, 3, 4, 2, 2, 3, 1] with offset 0
Looking for sum 3 in values of [2, 2, 3, 3, 4, 2, 2, 3, 1] with offset 1
Looking for sum 1 in values of [2, 3, 3, 4, 2, 2, 3, 1] with offset 2
Looking for sum 0 in values of [] with offset 10
Index: Group Size
0: 1
1: 2
9: 1
Remaining q=[2, 3, 3, 4, 2, 2, 3]
q=[1, 2, 3, 2, 3, 4, 2, 2, 3, 2]
Looking for sum 4 in values of [1, 2, 3, 2, 3, 4, 2, 2, 3, 2] with offset 0
Looking for sum 3 in values of [2, 3, 2, 3, 4, 2, 2, 3, 2] with offset 1
Looking for sum 1 in values of [3, 2, 3, 4, 2, 2, 3, 2] with offset 2
Failed to construct sum 1 from values in [3, 2, 3, 4, 2, 2, 3, 2]
Looking for sum 0 in values of [2, 3, 4, 2, 2, 3, 2] with offset 3
Index: Group Size
0: 1
2: 3
Remaining q=[2, 2, 3, 4, 2, 2, 3, 2]
q=[1, 2, 2]
Looking for sum 4 in values of [1, 2, 2] with offset 0
Looking for sum 3 in values of [2, 2] with offset 1
Looking for sum 1 in values of [2] with offset 2
Failed to construct sum 1 from values in [2]
Looking for sum 1 in values of [] with offset 3
Failed to construct sum 1 from values in []
Failed to construct sum 3 from values in [2, 2]
Looking for sum 2 in values of [2] with offset 2
Looking for sum 0 in values of [] with offset 3
Index: Group Size
1: 2
2: 2
Remaining q=[1]
q=[2, 3, 3]
Looking for sum 4 in values of [2, 3, 3] with offset 0
Looking for sum 2 in values of [3, 3] with offset 1
Failed to construct sum 2 from values in [3, 3]
Looking for sum 1 in values of [3] with offset 2
Failed to construct sum 1 from values in [3]
Looking for sum 1 in values of [] with offset 3
Failed to construct sum 1 from values in []
Failed to construct sum 4 from values in [2, 3, 3]
Could not construct sum 4 from values in [2, 3, 3]
如果我对问题的理解是正确的，那么您基本上尝试做的是对数字进行分组，使总和为 4 并且您优先考虑首先在队列中添加数字。
您可以使用动态规划方法来做到这一点。我在这里使用 int[] 和 int 作为总和，但问题可以推广到 most 数据结构。
首先你必须定义一个比较器，它比较索引的列表，例如字典序的：
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];
}
此方法 return 是 索引 的 ArrayList<Integer>，如果不能创建这样的组。它将根据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 - 如前所述 - 算法将 return null。在这种情况下，您必须发明一种回退机制。也许 return 组与 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 -> []
现在我们的 当前最佳解决方案 生成一个总和为四个的组已从 [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]。
顺序不同
这种方法可以推广，在 List<T> 上提供不同的 Comparator（这里是 LexComp<T>）将优先考虑另一个索引数组。比较器应始终至少满足传递性约束：如果 x 小于 y 并且 y 是小于 z：x 必须小于 z。此外，索引列表将始终增加。 [4,1,0] 的索引数组因此是不可能的。
我正在寻找一种方法来搜索给定序列中总和为给定数字（sum，此处为 4）且具有字典优先级的子序列。
以下面的例子为例：
1,2,2,4,1,1
不同的子序列可以加起来4。例如1,2,1、2,22,1,1。如果存在多个这样的序列，则应返回相应索引数组的字典序第一个：因此，如果可以用第一个元素找到这样的序列，则必须返回那个，否则，瞄准第二个和所以一个（迭代（取下一个）和递归（在第一个 select 之后，下一个但第一个也应该最接近序列的头部）。
所以对于这个例子，我们 select 1,2,1。现在还剩2,4,1。如果我们重复这个问题，我们就无法与 2 匹配：2,4 大于 4 并且 2,1 小于 4。因此我们 select 4。最后我们要select2和1.
这个概念的一个实际应用是过山车的队列。您需要 4 个人乘坐，但有些人和他们的朋友成群结队，希望所有人一起乘坐同一趟车。
在这个例子中1是排在最前面的一个人，2是他后面的一群2朋友。现在我们这次骑行总共需要 4 人，而我们已经有 3，所以我们插队（2 和 4）并带上第一个人，这给了我们总共 4 个人。
您可以遍历列表并按顺序添加，直到它大于您要查找的值。
代码：
public static int addListValues(int[] list, int num){//Returns number which can not be added by anything else in the list to be <= num.
boolean b[] = new boolean[list.length];//List of numbers already taken care of. True for not, false for cleared.
for(int i = 0; i < b.length; i++){
b[i] = true;
}
int count = 0;//Amount of numbers in int[] list which have been added to equal less than or equal to num.
int total = 0;
while(true){//loops until values left can not be added to equal or be less than num.
int check = 0;
for(int i = 0; i < list.length; i++){//Loops through list.
if(b[i]){//If the number has not been added already.
System.out.println("CHECKING: " + i);
if(total + list[i] > num){//Adds to check if the number is greater than num.
check++;
}
if(total + list[i] <= num){//Adds numbers together to equal num or less than num.
System.out.println("TEST: " + list[i] + " TOTAL: " + total);
if(total + list[i] != num){
boolean contains = false;
int index = 0;
for(int o = 0; o < list.length; o++){
if(list[o] == num - total && b[o] && o != i){
contains = true;
index = o;
break;
}
}
if(contains){
System.out.println("1: " + index + ", " + list[index]);
b[index] = false;
count++;
total = 0;
}else{
System.out.println("2");
b[i] = false;
count++;
total+= list[i];
}
}else{
System.out.println("3");
b[i] = false;
count++;
total = 0;
}
}else if(check == list.length - count){//Check if "check" is equal to the amount left over. In other words, if the numbers left are higher than the number you are looking for.
System.out.println("FINAL: 3");
int t = 0;
for(int j = 0; j < list.length; j++){
if(b[j]){
t += list[j];
}
}
return t;//More than one number is left and is higher than num. Returns numbers left added together
}else if(count == list.length-1){
System.out.println("FINAL: 2");
return list[i];//returns list[i] if it is the only number left over.
}
}else if(count >= list.length){
System.out.println("FINAL: 1");
return total;//Returns total if there is nothing left over. The total may be anything less than the "num".
}
}
}
}
我已经用多组数字测试了这个方法并且有效。如果遗留的值超过 4 个，我不确定 return 该怎么办，所以我添加了遗留的值并 return 编辑了这个。
此代码不需要任何导入。
这个问题的正确答案在很大程度上取决于您如何定义优先级。
如果可能，我们应该总是选择队伍中的第一组，还是让尽可能多的人排在队伍前面是最佳解决方案？
即给出
1, 2, 2, 3, 3, 4, 2, 2, 3, 1
是最优解
1, 2, 1
或
1、3
为了让您开始，这里有一个执行第一个的递归解决方案：
private static List<Integer> getSumIndices(int sum, List<Integer> queue) {
return getSumIndices(sum, new ArrayList<>(queue), 0);
}
private static List<Integer> getSumIndices(int sum, List<Integer> queue, int offset) {
System.out.printf("Looking for sum %s in values of %s with offset %s%n", sum, queue, offset);
if(sum == 0) {
//Base case
return new ArrayList<>();
}
for(int i = 0; i < queue.size(); i++) {
int value = queue.get(i);
// Can we actually use this group
if(value <= sum) {
try {
// See if we can find the remainder if we use this group
ArrayList<Integer> list = new ArrayList<>();
list.add(i + offset);
list.addAll(getSumIndices(sum - value, queue.subList(i + 1, queue.size()), offset + i + 1));
return list;
} catch(IllegalArgumentException e) {
// We couldn 't, continue looking
}
}
}
// We could not construct the sum using the values in the queue
System.out.printf("Failed to construct sum %s from values in %s%n", sum, queue);
throw new IllegalArgumentException(String.format("Could not construct sum %s from values in %s%n", sum, queue));
}
结果：
q=[1, 2, 2, 3, 3, 4, 2, 2, 3, 1]
Looking for sum 4 in values of [1, 2, 2, 3, 3, 4, 2, 2, 3, 1] with offset 0
Looking for sum 3 in values of [2, 2, 3, 3, 4, 2, 2, 3, 1] with offset 1
Looking for sum 1 in values of [2, 3, 3, 4, 2, 2, 3, 1] with offset 2
Looking for sum 0 in values of [] with offset 10
Index: Group Size
0: 1
1: 2
9: 1
Remaining q=[2, 3, 3, 4, 2, 2, 3]
q=[1, 2, 3, 2, 3, 4, 2, 2, 3, 2]
Looking for sum 4 in values of [1, 2, 3, 2, 3, 4, 2, 2, 3, 2] with offset 0
Looking for sum 3 in values of [2, 3, 2, 3, 4, 2, 2, 3, 2] with offset 1
Looking for sum 1 in values of [3, 2, 3, 4, 2, 2, 3, 2] with offset 2
Failed to construct sum 1 from values in [3, 2, 3, 4, 2, 2, 3, 2]
Looking for sum 0 in values of [2, 3, 4, 2, 2, 3, 2] with offset 3
Index: Group Size
0: 1
2: 3
Remaining q=[2, 2, 3, 4, 2, 2, 3, 2]
q=[1, 2, 2]
Looking for sum 4 in values of [1, 2, 2] with offset 0
Looking for sum 3 in values of [2, 2] with offset 1
Looking for sum 1 in values of [2] with offset 2
Failed to construct sum 1 from values in [2]
Looking for sum 1 in values of [] with offset 3
Failed to construct sum 1 from values in []
Failed to construct sum 3 from values in [2, 2]
Looking for sum 2 in values of [2] with offset 2
Looking for sum 0 in values of [] with offset 3
Index: Group Size
1: 2
2: 2
Remaining q=[1]
q=[2, 3, 3]
Looking for sum 4 in values of [2, 3, 3] with offset 0
Looking for sum 2 in values of [3, 3] with offset 1
Failed to construct sum 2 from values in [3, 3]
Looking for sum 1 in values of [3] with offset 2
Failed to construct sum 1 from values in [3]
Looking for sum 1 in values of [] with offset 3
Failed to construct sum 1 from values in []
Failed to construct sum 4 from values in [2, 3, 3]
Could not construct sum 4 from values in [2, 3, 3]
如果我对问题的理解是正确的，那么您基本上尝试做的是对数字进行分组，使总和为 4 并且您优先考虑首先在队列中添加数字。
您可以使用动态规划方法来做到这一点。我在这里使用 int[] 和 int 作为总和，但问题可以推广到 most 数据结构。
首先你必须定义一个比较器，它比较索引的列表，例如字典序的：
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];
}
此方法 return 是 索引 的 ArrayList<Integer>，如果不能创建这样的组。它将根据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 - 如前所述 - 算法将 return null。在这种情况下，您必须发明一种回退机制。也许 return 组与 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 -> []
现在我们的 当前最佳解决方案 生成一个总和为四个的组已从 [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]。
顺序不同
这种方法可以推广，在 List<T> 上提供不同的 Comparator（这里是 LexComp<T>）将优先考虑另一个索引数组。比较器应始终至少满足传递性约束：如果 x 小于 y 并且 y 是小于 z：x 必须小于 z。此外，索引列表将始终增加。 [4,1,0] 的索引数组因此是不可能的。