import com.vincent.rsf.framework.common.Cools;
import org.apache.commons.codec.digest.Md5Crypt;

import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationFinder {

    public 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
    }

    private 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;
    }

    private 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;
    }

    private 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 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);
        }
    }

    public static void main(String[] args) {
//        CombinationFinder finder = new CombinationFinder();
//        double[] nums = {3.0, 1.0, 4.0, 2.0};
//        double target = 0.1;
//        List<Integer> result = finder.findCombination(nums, target);
//        System.out.println("最优组合的索引: " + result); // 例如，等值组合可能为索引2（4.0）和3（1.0）
        System.out.println(Cools.md5("123456"));
    }
}