贪心算法最优装载问题(Java代码实现)

举报
ruochen 发表于 2021/03/27 23:30:01 2021/03/27
【摘要】 最优装载问题 最优装载问题实质上就是一个简单版的0-1背包问题 问题描述 有一批集装箱要装上一艘载重量为 c 的轮船,其中集装箱 i 的重量为 wi最优装载问题要求确定在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船 算法描述 可用贪心算法求解采用重量最轻者先装的贪心选择策略,可产生最优装载问题的最优解 Java 源代码 代码有详细注...

最优装载问题

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

问题描述

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

算法描述

  • 可用贪心算法求解
  • 采用重量最轻者先装的贪心选择策略,可产生最优装载问题的最优解

Java 源代码

代码有详细注释,不懂评论下方留言

/*
 * 若尘
 */
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]

  
 

文章来源: ruochen.blog.csdn.net,作者:若尘,版权归原作者所有,如需转载,请联系作者。

原文链接:ruochen.blog.csdn.net/article/details/106479576

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。