/**
 * 活动安排问题
 */
public class GreedySelector {
    public static void main(String[] args) {

        // 下标从 1 开始,存储活动开始时间
        int[] s = {1,3,0,5,3,5,6,8,8,2,12};
        // 下标从 1 开始,存储活动结束时间(排序好的，结束时间是递增的)
        int[] f = {4,5,6,7,8,9,10,11,12,13,14};

        boolean[] A = new boolean[s.length];

        System.out.println("各活动的开始时间,结束时间分别为：");

        for (int i = 0; i < s.length; i++) {
            System.out.println("["+i+"]:"+"("+s[i]+","+f[i]+")");
        }

        greedySelector(s, f, A);

        System.out.println("最大相容活动子集为：");

        for (int i = 0; i < s.length; i++) {
            if (A[i]) {
                System.out.println("["+i+"]:("+s[i]+","+f[i]+")");
            }
        }
    }

    public static void greedySelector(int[] s, int[] f, boolean[] A) {
        A[0] = true;
        int prev = 0; // prev用来记录最近一次加入A的活动

        for (int i = 1; i < s.length; i++) {
            if (s[i] >= f[prev]) {   // 后一个活动的开始时间 大于 前一个活动的结束时间
                A[i] = true;
                prev = i;
            } else {
                A[i] = false;
            }
        }
    }

}

最优装载问题

import java.util.Arrays;

/**
 * 最优装载问题
 */
public class Loading {
    public static void main(String[] args) {
        int most_w = 70;
        int[] w = {20,10,26,15};
        int[] x = new int[w.length];
        System.out.println("轮船载重为："+most_w);
        System.out.println("待装物品的重量分别为：");
        for (int i = 0; i < w.length; i++) {
            System.out.print(w[i]+" ");
        }
        loading(w, most_w, x);
        System.out.println();
        System.out.println("贪心选择结果为:");
        for (int i = 0; i < x.length; i++) {
            System.out.print(x[i]+" ");
        }

    }

    /**
     * 最优装载
     * @param w：各个物品的重量
     * @param most_w：轮船最大承载重量
     * @param x：构造最优解
     */
    public static void loading(int[] w, int most_w, int[] x) {
        int[] t = new int[w.length];    // 用来存储原始w数组的下标
        selectSort(w, t);

        for (int i = 0; i < w.length; i++) {
            // 若轮船还能放下
            if (w[t[i]] <= most_w) {
                x[t[i]] = 1;    // 将该物品的下标设为1
                most_w -= w[t[i]];  // 轮船载重减小
            }
        }
    }

    /**
     * 对 w数组 的下标进行排序
     * @param w： 存放各个物品重量
     * @param t： 存储 排序 后的w的下标
     */
    public static void selectSort(int[] w, int[] t) {
        // 将 w 拷贝到临时数组 tempArray 中
        int[] tempArr = Arrays.copyOfRange(w, 0, w.length);
        // 用来存储原始w数组的下标
        for (int i = 0; i < w.length; i++) {
            t[i] = i;
        }
        // 对w数组的副本进行排序（选择排序）
        int min = 0;
        for (int i = 0; i < tempArr.length; i++) {
            min = i;
            for (int j = i+1; j < tempArr.length; j++) {
                if (tempArr[min] > tempArr[j])
                    min = j;
            }
            // 同时交换副本数组-tempArr 以及 记录w下标的数组-t
            swap(tempArr, i, min);
            swap(t, i, min);
        }
    }

    // 交换
    public static void swap(int[] arr, int ind1, int ind2) {
        int temp = arr[ind1];
        arr[ind1] = arr[ind2];
        arr[ind2] = temp;
    }
}