From 1ea84a23004ebcfaf86cb436d84164602ca9091d Mon Sep 17 00:00:00 2001
From: skyouc
Date: 星期五, 08 八月 2025 17:03:36 +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 | 174 +++++++++++++++++++++++++++++++++++++++++++--------------
1 files changed, 131 insertions(+), 43 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
index 7ada63a..a3704cb 100644
--- 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
@@ -6,9 +6,9 @@
import java.util.stream.Collectors;
/**
+ * @param
* @author Ryan
* @description 鏍规嵁瀵硅薄澶氫釜灞炴�у悎骞跺鐞�
- * @param
* @return
* @time 2025/4/25 10:55
*/
@@ -46,9 +46,9 @@
}
/**
+ * @param
* @author Ryan
* @description 鐢ㄤ簬瀛樺偍澶氫釜鍒嗙粍閿殑鍐呴儴绫�
- * @param
* @return
* @time 2025/4/25 10:56
*/
@@ -80,52 +80,140 @@
}
- 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);
+ /**
+ * @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;
}
- // 濡傛灉宸茬粡鎵惧埌绮剧‘瑙ｏ紝涓嶉渶瑕佺户缁悳绱㈡洿闀跨殑缁勫悎
- if (minDifference < EPSILON) {
+ // 澶勭悊澶т簬鐨勬儏鍐�
+ 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<>(); // 纭繚涓嶈繑鍥瀗ull
+ }
+
+ /**
+ * @author Ryan
+ * @description 浣跨敤鍔ㄦ�佽鍒掑鎵惧拰绛変簬鐩爣鍊肩殑鏈�灏戝厓绱犵粍鍚堛�傚姩鎬佽鍒掓暟缁刣p璁板綍杈惧埌姣忎釜鍜屾墍闇�鐨勬渶灏戝厓绱犳暟鐩紝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 < 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);
+ 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);
}
}
--
Gitblit v1.9.1