package com.vincent.rsf.server.manager.utils;
|
|
import java.util.*;
|
import java.util.function.BinaryOperator;
|
import java.util.function.Function;
|
import java.util.stream.Collectors;
|
|
/**
|
* @param
|
* @author Ryan
|
* @description 根据对象多个属性合并处理
|
* @return
|
* @time 2025/4/25 10:55
|
*/
|
public class OptimalAlgorithmUtil {
|
|
private static List<Double> bestSolution;
|
private static double target;
|
private static double minDifference;
|
private static final double EPSILON = 1e-10;
|
|
/**
|
* 根据多个属性分组合并对象列表
|
*
|
* @param list 待分组的对象列表
|
* @param mergers 合并函数，定义如何合并同一组中的对象
|
* @param keyGetters 分组属性的getter方法数组
|
* @param <T> 对象类型
|
* @param <K> 分组键类型
|
* @return 分组合并后的对象列表
|
*/
|
@SafeVarargs
|
public static <T, K> List<T> groupAndMerge(
|
List<T> list,
|
BinaryOperator<T> mergers,
|
Function<T, K>... keyGetters) {
|
|
return new ArrayList<>(list.stream()
|
.collect(Collectors.toMap(
|
item -> new GroupingKeys<>(Arrays.stream(keyGetters)
|
.map(getter -> getter.apply(item))
|
.toArray()),
|
Function.identity(),
|
mergers))
|
.values());
|
}
|
|
/**
|
* @param
|
* @author Ryan
|
* @description 用于存储多个分组键的内部类
|
* @return
|
* @time 2025/4/25 10:56
|
*/
|
private static class GroupingKeys<K> {
|
private final Object[] keys;
|
private final int hashCode;
|
|
public GroupingKeys(Object[] keys) {
|
this.keys = keys;
|
this.hashCode = Arrays.deepHashCode(keys);
|
}
|
|
@Override
|
public boolean equals(Object o) {
|
if (this == o) {
|
return true;
|
}
|
if (o == null || getClass() != o.getClass()) {
|
return false;
|
}
|
GroupingKeys<?> that = (GroupingKeys<?>) o;
|
return Arrays.deepEquals(keys, that.keys);
|
}
|
|
@Override
|
public int hashCode() {
|
return hashCode;
|
}
|
}
|
|
|
/**
|
* @param
|
* @return
|
* @author Ryan
|
* @description 获取全拖或非全拖库位
|
* @time 2025/4/28 09:41
|
*/
|
public static List<Integer> findCombination(double[] nums, Double target) {
|
// 处理等值情况
|
List<Integer> equal = findEqual(nums, target);
|
if (equal != null && !equal.isEmpty()) {
|
return equal;
|
}
|
|
// 处理大于的情况
|
List<Integer> greater = findGreater(nums, target);
|
if (greater != null && !greater.isEmpty()) {
|
return greater;
|
}
|
|
// 处理小于的情况
|
List<Integer> less = findLess(nums, target);
|
return less != null ? less : new ArrayList<>(); // 确保不返回null
|
}
|
|
/**
|
* @author Ryan
|
* @description 使用动态规划寻找和等于目标值的最少元素组合。动态规划数组dp记录达到每个和所需的最少元素数目，prev数组记录路径以便回溯找到具体索引。
|
* @param
|
* @return
|
* @time 2025/4/28 12:33
|
*/
|
private static List<Integer> findEqual(double[] nums, double target) {
|
int n = nums.length;
|
double[] dp = new double[(int) (target * 100 + 1)]; // 放大100倍处理精度问题
|
Arrays.fill(dp, Double.MAX_VALUE);
|
dp[0] = 0;
|
int[] prev = new int[(int) (target * 100 + 1)];
|
Arrays.fill(prev, -1);
|
|
for (int j = 0; j < n; j++) {
|
int num = (int) (nums[j] * 100); // 放大100倍处理精度问题
|
for (int i = (int) (target * 100); i >= num; i--) {
|
if (dp[i - num] != Double.MAX_VALUE && dp[i - num] + 1 < dp[i]) {
|
dp[i] = dp[i - num] + 1;
|
prev[i] = j;
|
}
|
}
|
}
|
|
if (dp[(int) (target * 100)] == Double.MAX_VALUE) {
|
return null;
|
}
|
|
List<Integer> indices = new ArrayList<>();
|
int current = (int) (target * 100);
|
while (current > 0) {
|
int j = prev[current];
|
if (j == -1) return null;
|
indices.add(j);
|
current -= (int) (nums[j] * 100);
|
}
|
|
return indices;
|
}
|
|
/**
|
* @author Ryan
|
* @description 将数组降序排序后，贪心地累加元素直到总和超过目标值，返回这些元素的索引
|
* @param
|
* @return
|
* @time 2025/4/28 12:34
|
*/
|
private static List<Integer> findGreater(double[] nums, double target) {
|
List<double[]> sorted = new ArrayList<>();
|
for (int i = 0; i < nums.length; i++) {
|
sorted.add(new double[]{nums[i], i});
|
}
|
sorted.sort((a, b) -> Double.compare(b[0], a[0]));
|
|
double sum = 0;
|
List<Integer> indices = new ArrayList<>();
|
for (double[] pair : sorted) {
|
sum += pair[0];
|
indices.add((int) pair[1]);
|
if (sum > target) {
|
return indices;
|
}
|
}
|
|
return null;
|
}
|
|
/**
|
* @author Ryan
|
* @description 使用回溯法生成所有可能的组合，寻找总和最大但不超过目标值的组合，并记录元素数目最少的组合。
|
* @param
|
* @return
|
* @time 2025/4/28 12:34
|
*/
|
private static List<Integer> findLess(double[] nums, double target) {
|
int n = nums.length;
|
List<Integer> bestIndices = new ArrayList<>();
|
double[] maxSum = {-1.0};
|
for (int k = 1; k <= n; k++) {
|
List<Integer> currentIndices = new ArrayList<>();
|
double[] currentMax = {-1.0};
|
backtrack(nums, target, 0, k, 0.0, 0, currentIndices, currentMax, new ArrayList<>());
|
if (currentMax[0] != -1.0) {
|
if (currentMax[0] > maxSum[0] || (currentMax[0] == maxSum[0] && currentIndices.size() < bestIndices.size())) {
|
maxSum[0] = currentMax[0];
|
bestIndices = new ArrayList<>(currentIndices);
|
}
|
}
|
}
|
|
return bestIndices.isEmpty() ? null : bestIndices;
|
}
|
|
private static void backtrack(double[] nums, double target, int start, int k, double currentSum, int count, List<Integer> currentIndices, double[] currentMax, List<Integer> path) {
|
if (count == k) {
|
if (currentSum <= target && currentSum > currentMax[0]) {
|
currentMax[0] = currentSum;
|
currentIndices.clear();
|
currentIndices.addAll(path);
|
}
|
return;
|
}
|
|
for (int i = start; i < nums.length; i++) {
|
if (currentSum + nums[i] > target) continue;
|
path.add(i);
|
backtrack(nums, target, i + 1, k, currentSum + nums[i], count + 1, currentIndices, currentMax, path);
|
path.remove(path.size() - 1);
|
}
|
}
|
|
}
|
