最优装载问题

问题描述

• 有一批集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为w_i，最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

代码实现

public class Loading {

    public static void main(String[] args) {
        float[] w = {1, 3, 10, 5, 3, 5, 6, 8, 1, 2, 12};
        int n = w.length;
        Boolean[] x = new Boolean[n];
        float c = 30;
        Loading(x, w, c, n);
        for (int i = 0; i < n; i++) {
            System.out.printf("%3d: weight: %-6.2f load: %6b\n", i + 1, w[i], x[i]);
        }
    }

    public static void Loading(Boolean[] x, float[] w, float c, int n) {
        int[] t = new int[n];
        Sort(w, t, n);

        for (int i = 0; i < n; i++) {
            x[i] = false;
        }
        for (int i = 0; i < n && w[t[i]] <= c; i++) {
            x[t[i]] = true;
            c -= w[t[i]];
        }
    }

    public static void Sort(float[] w, int[] t, int n) {
        float[] array = w.clone();
        float temp;
        int index;
        for (int i = 0; i < n; i++) {
            t[i] = i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;

                    index = t[j];
                    t[j] = t[j + 1];
                    t[j + 1] = index;
                }
            }
        }
    }
}

• Loading(int[] x, int[] w, int c, int n)：采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。
  • int[] x：每件货物是否装入集装箱，x_i=1表示第i号货物装入集装箱，为0时则不装入集装箱。
  • int[] w：每件货物的重量，w_i表示第i号货物的重量。
  • int c：轮船的最大载重量。
  • int n：货物的数量。
• Sort(int[] w, int[] t, int n) ：对货物的重量由小到大排序，并将下标的顺序记录在数组n中。
  • int[] w：每件货物的重量，w_i表示第i号货物的重量。
  • int[] t：排序后w数组的下标顺序。
  • int n：数组的长度。