From 27b40d8451a39191dfbe4576415419ce2ed9cb2f Mon Sep 17 00:00:00 2001
From: skyouc
Date: 星期日, 27 四月 2025 18:28:03 +0800
Subject: [PATCH] Merge branch 'devlop' of http://47.97.1.152:5880/r/wms-master into devlop
---
rsf-server/src/main/java/com/vincent/rsf/server/manager/utils/OptimalAlgorithmUtil.java | 132 ++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 132 insertions(+), 0 deletions(-)
diff --git a/rsf-server/src/main/java/com/vincent/rsf/server/manager/utils/OptimalAlgorithmUtil.java b/rsf-server/src/main/java/com/vincent/rsf/server/manager/utils/OptimalAlgorithmUtil.java
new file mode 100644
index 0000000..7ada63a
--- /dev/null
+++ b/rsf-server/src/main/java/com/vincent/rsf/server/manager/utils/OptimalAlgorithmUtil.java
@@ -0,0 +1,132 @@
+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;
+
+/**
+ * @author Ryan
+ * @description 鏍规嵁瀵硅薄澶氫釜灞炴�у悎骞跺鐞�
+ * @param
+ * @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());
+ }
+
+ /**
+ * @author Ryan
+ * @description 鐢ㄤ簬瀛樺偍澶氫釜鍒嗙粍閿殑鍐呴儴绫�
+ * @param
+ * @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;
+ }
+ }
+
+
+ public static List<Double> findBestCombination(Double[] candidates, double targetSum) {
+ bestSolution = null;
+ target = targetSum;
+ minDifference = Double.MAX_VALUE;
+ Arrays.sort(candidates);
+ backtrack(candidates, 0, new ArrayList<>(), 0.0);
+
+ // 濡傛灉娌℃湁绮剧‘瑙ｏ紝杩斿洖鏈�鎺ヨ繎鐨勮繎浼艰В
+ return bestSolution != null ? bestSolution : new ArrayList<>();
+ }
+
+ private static void backtrack(Double[] candidates, int start,
+ List<Double> current, double currentSum) {
+ // 璁＄畻褰撳墠鍜屼笌鐩爣鐨勫樊鍊�
+ double difference = Math.abs(currentSum - target);
+
+ // 濡傛灉鎵惧埌鏇翠紭瑙ｏ紙宸�兼洿灏忔垨宸�肩浉鍚屼絾缁勫悎鏇寸煭锛�
+ if (difference < minDifference - EPSILON ||
+ (Math.abs(difference - minDifference) < EPSILON &&
+ (bestSolution == null || current.size() < bestSolution.size()))) {
+ minDifference = difference;
+ bestSolution = new ArrayList<>(current);
+ }
+
+ // 濡傛灉宸茬粡鎵惧埌绮剧‘瑙ｏ紝涓嶉渶瑕佺户缁悳绱㈡洿闀跨殑缁勫悎
+ if (minDifference < EPSILON) {
+ return;
+ }
+
+ // 閬嶅巻鍊欓�夋暟瀛�
+ for (int i = start; i < candidates.length; i++) {
+ double num = candidates[i];
+
+ // 鍓灊锛氬鏋滃綋鍓嶅拰宸茬粡杩滃ぇ浜庣洰鏍囧�硷紝璺宠繃
+ if (currentSum + num > target + minDifference + EPSILON) {
+ continue;
+ }
+
+ // 璺宠繃閲嶅鏁板瓧
+ if (i > start && Math.abs(candidates[i] - candidates[i - 1]) < EPSILON) {
+ continue;
+ }
+
+ current.add(num);
+ backtrack(candidates, i + 1, current, currentSum + num);
+ current.remove(current.size() - 1);
+ }
+ }
+
+}
\ No newline at end of file
--
Gitblit v1.9.1