#新增 1. 波次生成出库任务

skyouc

4 天以前 b0926b3d4379d087d5c0187882b98be0ed88da83

 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<>(); // 确保不返回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 < 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);
        }
    }