前一阵突然想到的一个有趣的问题。
我们知道，一般的策略对战类游戏，比如dota，lol，平台运营方都会提供天梯模式。就是把积分相近的用户集中在一起对战，这样更能增加一些游戏乐趣。
假设现在有1000-2000分段，2000-3000分段，3000-4000分段等等，现在系统从当前在排队的天梯用户中(比如1000-2000分段)，随机的挑选了10个玩家，假设是
1: 1001
2: 1237
3: 1123
4: 1479
5: 1921
6: 1371
7: 1520
8: 1632
9: 1823
我们要把这10个用户分成两组，每组5个人。如何分配才能尽可能公平？
基本的公平其实可以简化为，第一组用户的天梯分数累加后和第二组用户的天梯分数累加和差距最小。
我们把这个问题数学抽象下，已知一个数组data(2n) -> {data1, data2, data3 .... data2n}
如何设计一种分配策略，可以把数组分为数据个数相等的两个子数组：
a(n) -> {a1, a2, a3....an) 和 b(n) -> {b1, b2, b3 ...bn}，并且 |sum(a) - sum(b)| 最小。
首先想到的一种策略是这样的：使用贪心的方式，找到一种局部最优解，首先把10个用户按天梯分数从小到大进行排序。然后把排名第1的分到A组，把排名倒数第1的分到B组，之后再把排名第2的分到B组，把排名倒数第2的分到A组，如此直到最后两个人。
这样的分组方式，在大部分情况下可以获得不错的效果，但是并不是严格意义上的最优解。如果想要严格意义的最优解，该如何呢？
这个问题其实可以抽象成一个背包问题，从2n个数里选出n个数，使得sum(n)的值最接近sum(2n)/2。
但和传统意义上的背包又有不同，因为我们需要确定背包内数据的个数，所以并不是传统的01背包问题。
我们先抽象动态转移方程：
res[i][j][k] -> 从前i+1个数里选出j+1个，总和最接近(<=) k 的方案
res[i][j][k] = max{res[i-1][j][k](不包含data[i]), res[i-1][j-1][k-data[i]]+data[i](包含data[i])} (如果 k < data[i] 则返回res[i-1][j][k])
代码如下：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import javafx.util.Pair;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
/**
* Created by littlersmall on 2019/2/20.
*/
public class Ladder {
private List<Integer> testData1 = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
private List<Integer> testData2 = Arrays.asList(1, 2, 3, 4);
private List<Integer> testData3 = Arrays.asList(100, 90, 80, 70, 60, 50, 40, 30, 20, 10);
private List<Integer> testData4 = Arrays.asList(44, 22, 33, 77, 66, 11, 99, 55);
private List<Integer> testData5 = Arrays.asList(99, 2, 33, 7);
/*
* 从10个数里选5个数，使得总和最接近(<=) sum/2
*
* 动态规划问题，动态转移方程
* res[i][j][k] --- 从前i+1个数里选出j+1个，总和最接近(<=) k 的方案
* res[i][j][k] = max{res[i-1][j][k] (不包含data[i]), res[i-1][j-1][k-data[i]]+data[i](包含data[i])}
* 如果 k < data[i] res[i-1][j][k] (不包含data[i])
*/
public Pair<List<Integer>, List<Integer>> find(List<Integer> data) {
int length = data.size();
int sum = data.stream().mapToInt(value -> value).sum();
//初始化
Map<String, Solution> solutionMap = new HashMap<>();
for (int i = 1; i < length; i++) {
for (int j = 0; j < length / 2; j++) {
for (int k = 0; k <= sum / 2; k++) {
if (k < data.get(i)) {
//对于没法找到的情况，sum用默认的0
solutionMap.put(key(i, j, k), solutionMap.getOrDefault(key(i - 1, j, k), new Solution()));
} else {
Solution solution1 = solutionMap.getOrDefault(key(i - 1, j, k), new Solution());
Solution solution2 = solutionMap.getOrDefault(key(i - 1, j - 1, k - data.get(i)), new Solution());
if (solution1.getSum() < solution2.getSum() + data.get(i)
&& solution2.getNumberList().size() == j + 1 - 1) {
int curSum = solution2.getSum() + data.get(i);
List<Integer> curList = new ArrayList<>();
curList.addAll(solution2.getNumberList());
curList.add(data.get(i));
solutionMap.put(key(i, j, k), new Solution(curSum, curList));
} else {
solutionMap.put(key(i, j, k), solution1);
}
}
}
}
}
Solution solution = solutionMap.get(key(length - 1, length / 2 - 1, sum / 2));
if (solution != null && solution.getSum() > 0) {
List<Integer> list2 = data.stream()
//不考虑重复元素问题
.filter(value -> !solution.getNumberList().contains(value))
.collect(Collectors.toList());
return new Pair<>(solution.getNumberList(), list2);
}
return null;
}
public static void main(String[] args) {
Ladder ladder = new Ladder();
System.out.println(ladder.find(ladder.testData1));
System.out.println(ladder.find(ladder.testData2));
System.out.println(ladder.find(ladder.testData3));
System.out.println(ladder.find(ladder.testData4));
System.out.println(ladder.find(ladder.testData5));
}
@NoArgsConstructor
@AllArgsConstructor
@Data
private static class Solution {
private int sum;
private List<Integer> numberList = new ArrayList<>();
}
private String key(int i, int j, int sum) {
return Stream.of(i, j, sum).map(num -> "" + num).collect(Collectors.joining("#"));
}
}
