java数据分组 动态规划 遗传算法

Question

n个小数待分组，每个数组k个，如果n%k==0,那么组数为n/k个，如果n%k!=0,则最后一组的数量为n%k,组数为n/K+1,要求每个组的均值相等或者相近！

Answer 1

import java.util.*;
import java.util.stream.Collectors;

import static java.util.stream.Collectors.*;

public class GroupTest {
public static void main(String[] args) {
double[] nums = {100.0, 1.0, 20.0, 50.0, 90.0, 91.0, 92.0, 31.0, 32.0, 63.0,
33.0, 45.0, 56.0, 78.0, 88.0, 99.0, 8.0, 13.0, 23.0, 53.0, 67.0};

    int k = 8;

    group(nums, k);
}

public static void group(double[] values, int countPerGroup) {
    // order first, get len%countPerGroup from middle
    // the left split to several groups

    // calculate the average, get len%countPerGroup numbers which totally to it
    // cycle, if min, select the max

    Arrays.sort(values);

    List<Double> lstNums = new ArrayList<>();
    for(double value: values) {
        lstNums.add(value);
    }

    List<Double> middleList = new ArrayList<>();
    int midLen = values.length%countPerGroup;

    if(midLen != 0) {
        middleList = middle(lstNums, midLen, Arrays.stream(values).average().getAsDouble());
    }

    List<List<Double>> lstGroups = new ArrayList<>();
    int groups = values.length/countPerGroup;
    for(int i = 0; i < groups; i++) {
        lstGroups.add(new ArrayList<>());
    }

    for(int i = 0; i < countPerGroup; i++) {
        lstGroups = lstGroups.stream().sorted((a, b) -> {
            double total_a = a.stream().reduce(0.0, Double::sum);
            double total_b = b.stream().reduce(0.0, Double::sum);
            return Double.compare(total_a, total_b);
        }).collect(Collectors.toList());

        lstGroups.forEach(group -> {
            group.add(max(lstNums));
        });
    }

    if(midLen != 0) {
        lstGroups.add(middleList);
    }
    lstGroups.forEach(group -> {
        System.out.println("average:" + group.stream().reduce(0.0, Double::sum)/group.size()
                + ", count:" + group.size()
        + ", elements:" + group.toString());
    });
}

public static List<Double> middle(List<Double> values, int count, double average) {
    List<Double> middleList = new ArrayList<>();

    if(count == 1) {
        middleList.add(mostNear(values, average));
    } else {
        List<Double> tmp = middle(values, count - 1, average);
        double total = 0.0;
        for(double value : tmp) {
            total = total + value;
        }

        middleList.addAll(tmp);
        middleList.add(mostNear(values, average * count - total));
    }


    return middleList;
}
public static double mostNear(List<Double> values, double average) {
    double nearestValue = 0.0;
    double gap = values.stream().max(Double::compareTo).get();
    for(double value: values) {
        if(Math.abs(value - average) < gap) {
            gap = Math.abs(value - average);
            nearestValue = value;
        } else {
            break;
        }
    }

    // remove from the list
    values.remove(nearestValue);
    return nearestValue;
}

public static double max(List<Double> values) {
    double maxValue = values.stream().max(Double::compareTo).get();

    values.remove(maxValue);
    return maxValue;
}

}