关于java:如何对一个数字列表进行等和划分

明天遇到了一个这样的问题

一个序列分成 n 段，要求各段和的差值的最大值最小
或者说，要求各段和尽可能靠近序列和 S / n
须要最优解，思路或者代码都行
理论利用场景：布局瀑布流排版

如果没有利用场景，其实这个问题还是比较复杂的，可能会波及到一些冀望预测类的货色
不过这里题主提供了利用场景，这个利用场景有一些特色，可能简化这个问题
特色 1：序列中的每个元素差别不会太大，不会呈现 >> 或 << 的状况
特色 2：序列个数不会太小，不会呈现边缘的极限状况
特色 3：段数不会太大
特色 4：是能够承受肯定的误差的

基于这些特色，一个简略的解题思路就有了
序列排序，从大到小往 N 个桶外面放，每次找桶内和最小的那个桶放以后值，循环至最初
数量越多误差越小

接下来上 demo 代码

public class MasonryLayout {

    // 初始化一个数字队列
    List<Integer> initData;
    // 记录分几个组
    int slotCount;

    class Node {
        int position;
        int weight;

        @Override
        public String toString() {return "Node{" + "position=" + position + ", weight=" + weight + '}';
        }

        public String print() {return "{" + position + "," + weight + '}';
        }
    }

    class Sums {
        int sum;
        List<Node> nodeList;

        public Sums(int sum) {
            this.sum = sum;
            nodeList = new ArrayList<>();}

        public void addNode(Node node) {nodeList.add(node);
            sum += node.weight;
        }

        @Override
        public String toString() {return "Sums{" + "sum=" + sum + '}';
        }

        public String print() {
            // 按地位升序从新排一下
            nodeList.sort(Comparator.comparingInt(o -> o.position));
            return "SUM:" + sum + "Nodes:" + nodeList.stream().map(node -> node.print()).collect(Collectors.joining("-"));
        }
    }

    public MasonryLayout(int basic, int length, int slotCount) {
        // 这里只是造模仿数据的代码
        initData = new ArrayList<>();
        Random random = new Random();
        int seed = random.nextInt(basic) + basic;
        System.out.println("seed:" + seed);
        for (int i = 0; i < length; i++) {int num = random.nextInt(basic / 2) + seed;
            initData.add(num);
        }
        this.slotCount = slotCount;
        System.out.println("原始数据:" + initData);
    }

    void execute() {
        // 保留排序后的节点
        List<Node> sortData = new ArrayList<>();
        TreeSet<Sums> sumSet = makeTreeSet();
        for (int i = 0; i < slotCount; i++) {sumSet.add(new Sums(0));
        }

        for (int i = 0; i < initData.size(); i++) {Node node = new Node();
            node.position = i;
            node.weight = initData.get(i);
            sortData.add(node);
        }
        // 降序所有 Node，这里要从大到小取数
        sortData.sort((o1, o2) -> o2.weight - o1.weight);
        System.out.println(sortData);
        for (Node node : sortData) {sumSet.first().addNode(node);
            TreeSet<Sums> sumSet1 = sumSet;
            sumSet = makeTreeSet();
            sumSet.addAll(sumSet1);
        }
        sumSet.forEach(sums -> {System.out.println("分段:" + sums.print());
        });
    }

    TreeSet<Sums> makeTreeSet() {return new TreeSet<>(new Comparator<Sums>() {
            @Override
            public int compare(Sums o1, Sums o2) {
                // 升序，这里要取最小值
                int ret = o1.sum - o2.sum;
                if (ret == 0) {return o1.hashCode() - o2.hashCode();} else {return ret;}
            }
        });
    }

    public static void main(String[] args) {MasonryLayout masonryLayout = new MasonryLayout(20, 60, 4);
        masonryLayout.execute();}
}

执行一下
后果

原始数据: [44, 36, 43, 41, 40, 44, 40, 40, 37, 40, 36, 39, 43, 36, 41, 39, 36, 36, 44, 44, 38, 41, 38, 38, 36, 39, 43, 38, 44, 38, 36, 37, 43, 44, 40, 37, 37, 39, 44, 43, 40, 38, 39, 37, 42, 38, 40, 38, 42, 39, 36, 40, 40, 36, 39, 43, 44, 35, 38, 37]

分段: SUM: 593 Nodes: {4, 40}-{5, 44}-{6, 40}-{11, 39}-{12, 43}-{23, 38}-{24, 36}-{31, 37}-{33, 44}-{40, 40}-{42, 39}-{45, 38}-{55, 43}-{57, 35}-{59, 37}
分段: SUM: 593 Nodes: {1, 36}-{3, 41}-{7, 40}-{13, 36}-{15, 39}-{18, 44}-{26, 43}-{27, 38}-{30, 36}-{35, 37}-{38, 44}-{44, 42}-{46, 40}-{47, 38}-{49, 39}
分段: SUM: 593 Nodes: {9, 40}-{10, 36}-{14, 41}-{16, 36}-{19, 44}-{25, 39}-{29, 38}-{32, 43}-{36, 37}-{48, 42}-{50, 36}-{51, 40}-{54, 39}-{56, 44}-{58, 38}
分段: SUM: 594 Nodes: {0, 44}-{2, 43}-{8, 37}-{17, 36}-{20, 38}-{21, 41}-{22, 38}-{28, 44}-{34, 40}-{37, 39}-{39, 43}-{41, 38}-{43, 37}-{52, 40}-{53, 36}

下面 Nodes 中{原始地位，原始数值}

欢送关注公众号，独特交换，共同进步