前一陣突然想到的一個(gè)有趣的問題扇雕。
我們知道，一般的策略對(duì)戰(zhàn)類游戲募书，比如dota绪囱，lol，平臺(tái)運(yùn)營方都會(huì)提供天梯模式莹捡。就是把積分相近的用戶集中在一起對(duì)戰(zhàn)鬼吵，這樣更能增加一些游戲樂趣。
假設(shè)現(xiàn)在有1000-2000分段篮赢，2000-3000分段齿椅，3000-4000分段等等琉挖，現(xiàn)在系統(tǒng)從當(dāng)前在排隊(duì)的天梯用戶中(比如1000-2000分段)，隨機(jī)的挑選了10個(gè)玩家涣脚，假設(shè)是
1: 1001
2: 1237
3: 1123
4: 1479
5: 1921
6: 1371
7: 1520
8: 1632
9: 1823
我們要把這10個(gè)用戶分成兩組粹排，每組5個(gè)人。如何分配才能盡可能公平涩澡？
基本的公平其實(shí)可以簡化為，第一組用戶的天梯分?jǐn)?shù)累加后和第二組用戶的天梯分?jǐn)?shù)累加和差距最小坠敷。

我們把這個(gè)問題數(shù)學(xué)抽象下妙同，已知一個(gè)數(shù)組data(2n) -> {data1, data2, data3 .... data2n}
如何設(shè)計(jì)一種分配策略，可以把數(shù)組分為數(shù)據(jù)個(gè)數(shù)相等的兩個(gè)子數(shù)組：
a(n) -> {a1, a2, a3....an) 和 b(n) -> {b1, b2, b3 ...bn}膝迎，并且 |sum(a) - sum(b)| 最小粥帚。

首先想到的一種策略是這樣的：使用貪心的方式，找到一種局部最優(yōu)解限次，首先把10個(gè)用戶按天梯分?jǐn)?shù)從小到大進(jìn)行排序芒涡。然后把排名第1的分到A組，把排名倒數(shù)第1的分到B組卖漫，之后再把排名第2的分到B組费尽，把排名倒數(shù)第2的分到A組，如此直到最后兩個(gè)人羊始。
這樣的分組方式旱幼，在大部分情況下可以獲得不錯(cuò)的效果，但是并不是嚴(yán)格意義上的最優(yōu)解突委。如果想要嚴(yán)格意義的最優(yōu)解柏卤，該如何呢？

這個(gè)問題其實(shí)可以抽象成一個(gè)背包問題匀油，從2n個(gè)數(shù)里選出n個(gè)數(shù)缘缚，使得sum(n)的值最接近sum(2n)/2。
但和傳統(tǒng)意義上的背包又有不同敌蚜，因?yàn)槲覀冃枰_定背包內(nèi)數(shù)據(jù)的個(gè)數(shù)桥滨，所以并不是傳統(tǒng)的01背包問題。
我們先抽象動(dòng)態(tài)轉(zhuǎn)移方程：

res[i][j][k] -> 從前i+1個(gè)數(shù)里選出j+1個(gè)弛车，總和最接近(<=) 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個(gè)數(shù)里選5個(gè)數(shù)该园，使得總和最接近(<=) sum/2
     *
     * 動(dòng)態(tài)規(guī)劃問題，動(dòng)態(tài)轉(zhuǎn)移方程
     * res[i][j][k] --- 從前i+1個(gè)數(shù)里選出j+1個(gè)帅韧，總和最接近(<=) 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)) {
                        //對(duì)于沒法找到的情況里初，sum用默認(rèn)的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()
                    //不考慮重復(fù)元素問題
                    .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("#"));
    }
}