V2CE – 贪心算法最优装载问题（Java代码实现）

最优装载问题

最优装载问题实质上就是一个简单版的0-1背包问题

问题描述

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

算法描述

  • 可用贪心算法求解/*
    * 若尘
    */
    package loading;

import java.util.Arrays;

/**

* 最优装载问题（贪心算法）

* @author ruochen

* @version 1.0

*/

public class LoadingProblem {

private static int[] x; 

/\*\*

 \* 

 \* @param c 总重量

 \* @param w 每个集装箱的重量

 \* @param x 记录是否装入 （1： 装入    0： 不装入）

 \* @return

 \*/

public static float Loading(float c, float[] w, int[] x) {

	int n = w.length;

	Element[] d = new Element[n];

	for (int i = 0; i < n; i++) {

		// 初始化

		d[i] = new Element(w[i], i);

	}

	Arrays.sort(d);

	// 记录最优值

	float opt = 0;

	for (int i = 0; i < n; i++) {

		// 初始化 

		x[i] = 0;

	}

	for (int i = 0; i < n && d[i].w <= c; i++) {

		x[d[i].i] = 1;

		opt += d[i].w;

		c -= d[i].w;

	}

	return opt;

}

public static void main(String[] args) {

	float c = 10;

	float[] w = new float[]{4, 2, 5, 1, 3};

	x = new int[w.length];

	float opt = Loading(c, w, x);

	System.out.println("最优值为: " + opt);

	System.out.println("最优解为： " + Arrays.toString(x));

}

public static class Element implements Comparable<Element> {

	float w;

	int i;

	public Element(float w, int i) {

		this.w = w;

		this.i = i;

	}

	/\*\*

	 \* 按照升序排列

	 \*/

	@Override

	public int compareTo(Element o) {

		if (this.w < o.w) 

			return -1;

		else if (this.w == o.w)

			return 0;

		else 

			return 1;

	}

}

}最优值为: 10.0

最优解为： 1, 1, 0, 1, 1

  • 采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解Java 源代码代码有详细注释，不懂评论下方留言
正文完
2021-09-15