用Java写个贪心算法

以下是一个用Java编写的贪心算法示例，该算法用于找到一组数中最接近目标值的子集。

import java.util.*;

public class GreedyAlgorithm {
    
    public static List<Integer> findClosestSubset(List<Integer> numbers, int target) {
        // 按升序排序输入的数字集合
        Collections.sort(numbers);
        
        List<Integer> subset = new ArrayList<>();
        int sum = 0;
        
        // 从最小值开始，逐个添加数字，直到总和超过目标值
        for (int i = 0; i < numbers.size() && sum < target; i++) {
            int num = numbers.get(i);
            if (sum + num <= target) {
                subset.add(num);
                sum += num;
            }
        }
        
        // 如果总和小于目标值，则再添加一个最大值
        if (sum < target && !numbers.isEmpty()) {
            subset.add(numbers.get(numbers.size() - 1));
        }
        
        return subset;
    }
    
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 3, 5, 7, 9);
        int target = 12;
        
        List<Integer> subset = findClosestSubset(numbers, target);
        System.out.println("Closest subset to " + target + " is: " + subset);
    }
}

在这个算法中，我们首先对输入的数字集合进行排序，然后从最小的数字开始，逐个添加数字，直到总和超过目标值。如果总和小于目标值，则再添加最大的数字。这个算法的时间复杂度为O(nlogn)，其中n是数字集合的大小。