你可以通过先计算所有可能性，然后再进行排序来解决这个问题。如果你能发现一个有趣的规律，找到所有可能性并不那么复杂。让我们举个例子：
a
=======
[a]
如果您只有一个输入
a，唯一可能的结果是
[a]。
a, b
==============
[a] [a, b]
[b]
如果您的输入为
a，b，则有3种可能的结果：
[a]，[b]，[a，b]。
这就是我们发现规则1的地方：单个元素（
[a]）的可能性是
a，b中可能性的一个
子集。或者概括一下：
所有先前结果的可能性都将包含在当前结果中。
让我们看看对于
a，b，c是否成立：
a, b a, b, c
================== =============================
-------------- -------------
| [a] [a, b] | | [a] [a, b] |
| [b] | | [b] |
|--------------| |-------------| [a, b, c]
[c] [a, c]
[b, c]
你可以验证更大的输入，但它总是成立的。如果你从更广阔的角度来看待这个问题，这一切都是有道理的。潜在的n的所有组合将是：潜在的n-1的所有组合加上一些额外的组合。
但是这里还有另一个更有趣的规则。
如果您有这样的输入：
a, b
==============
[a] [a, b]
[b]
你可以创建一个算法来计算下一个。首先创建前一个的副本（因为上面的规则）：
a, b, c
==============
[a] [a, b]
[b]
对于第一行，你只需要添加“last”后面的字母。由于下一个是
a, b, c，所以你只需要在第一行中添加：
c：
a, b, c
==============
[a] [a, b]
[b]
[c]
对于第二行，你需要使用前一行（减去添加的
c），并添加“下一个”字母，然后插入它。也就是说：
a, b, c
===================
[a] <-| [a, b]
[b] |-> [a, c] <
[c]
对于一些b:
a, b, c
===================
[a] [a, b]
[b] <-| [a, c]
[c] |-> [b, c] <-- "b" came from the previous row, "c" then added as the last one
对于最后一行，我们只需将所有的“下一个”（a、b、c）相加：
a, b, c
=================================
[a] [a, b]
[b] [a, c] [a, b, c]
[c] [b, c]
使用上述相同的逻辑，您可以计算出a、b、c、d的结果：
首先复制：
a, b, c, d
=================================
[a] [a, b]
[b] [a, c] [a, b, c]
[c] [b, c]
添加 d：
a, b, c, d
=================================
[a] [a, b]
[b] [a, c] [a, b, c]
[c] [b, c]
[d]
取上一行并追加：
a, b, c, d
=================================
[a] [a, b]
[b] [a, c] [a, b, c]
[c] [b, c]
[d] [a, d]
[b, d]
[c, d]
再次，取出前一行并附加（记住：“除了已添加的行”）：
a, b, c, d
=================================
[a] [a, b]
[b] [a, c] [a, b, c]
[c] [b, c] [a, b, d] <--- [a, b] + [d]
[d] [a, d] [a, c, d] <--- [a, c] + [d]
[b, d] [b, c, d] <--- [b, c] + [d]
[c, d]
最后一个：
a, b, c, d
=================================================
[a] [a, b]
[b] [a, c] [a, b, c]
[c] [b, c] [a, b, d]
[d] [a, d] [a, c, d] [a, b, c, d]
[b, d] [b, c, d]
[c, d]
如果你理解上面发生的事情，那就是关于编写代码的一切。我所做的唯一更改是不添加我已经知道会未通过与max检查的元素。这就是它，看起来很复杂，但实际上它相当简单（除了一些边缘情况的例外）：
static List<String> partitions(List<Choice> all, int max) {
ArrayList<ArrayList<ArrayList<Choice>>> previousResult = new ArrayList<>();
ArrayList<ArrayList<ArrayList<Choice>>> currentResult = new ArrayList<>();
int i = 0;
for(;i<all.size();++i) {
Choice current = all.get(i);
if(currentResult.isEmpty()) {
if(less(List.of(current), max)) {
ArrayList<Choice> inner = new ArrayList<>();
inner.add(current);
ArrayList<ArrayList<Choice>> in = new ArrayList<>();
in.add(inner);
currentResult.add(in);
previousResult.add(in);
}
} else {
if(less(List.of(current), max)) {
ArrayList<Choice> element = new ArrayList<>();
element.add(current);
currentResult.get(0).add(element);
}
if(currentResult.size() > 1) {
for(int j=0;j<i-1;++j) {
if(j < previousResult.size()) {
ArrayList<ArrayList<Choice>> p = previousResult.get(j);
for(int d=0;d<=p.size()-1;++d){
ArrayList<Choice> copy = new ArrayList<>(p.get(d));
copy.add(all.get(i));
if(less(copy, max)){
currentResult.get(j).add(copy);
}
}
}
}
}
ArrayList<ArrayList<Choice>> tail = new ArrayList<>();
ArrayList<Choice> t = new ArrayList<>(all.subList(0, i + 1));
if(less(t, max)) {
tail.add(t);
currentResult.add(tail);
}
if(currentResult.size() == 1) {
ArrayList<Choice> l = currentResult.get(0).stream().flatMap(List::stream).collect(Collectors.toCollection(ArrayList::new));
if(less(l, max)) {
tail.add(l);
currentResult.add(tail);
}
}
previousResult = copy(previousResult, currentResult);
}
}
return
currentResult.stream()
.flatMap(List::stream)
.map(list -> {
int sum = list.stream().mapToInt(Choice::getCost).sum();
List<String> l = list.stream().map(Choice::getKey).collect(Collectors.toList());
return new AbstractMap.SimpleEntry<>(sum, l);
})
.sorted(Map.Entry.<Integer, List<String>>comparingByKey().reversed())
.filter(x -> x.getKey() <= max)
.map(Map.Entry::getValue)
.findFirst()
.orElse(List.of());
}
private static ArrayList<ArrayList<ArrayList<Choice>>> copy(ArrayList<ArrayList<ArrayList<Choice>>> previousResult, ArrayList<ArrayList<ArrayList<Choice>>> currentResult) {
return currentResult.stream()
.map(x -> x.stream().map(y -> (ArrayList<Choice>)y.clone()).collect(Collectors.toCollection(ArrayList::new)))
.collect(Collectors.toCollection(ArrayList::new));
}
private static boolean less(List<Choice> in, int max) {
return in.stream().mapToInt(Choice::getCost).sum() <= max;
}
