回溯法最优装载问题(Java实现)

举报
ruochen 发表于 2021/03/28 01:34:33 2021/03/28
【摘要】 最优装载问题 问题描述 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量为wi,装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这2艘轮船。如果有,找出一种装载方案。例如:当n=3,c1=c2=50,且w=[10,40,40]时,则可以将集装箱1和2装到第一艘轮船上 Java源代码 注释很详细 /* * 若尘...

最优装载问题

问题描述

  • 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量为wi,装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这2艘轮船。如果有,找出一种装载方案。例如:当n=3,c1=c2=50,且w=[10,40,40]时,则可以将集装箱1和2装到第一艘轮船上

Java源代码

注释很详细

 /*
 * 若尘
 */
package loading2;

/**
 * 装载问题
 * @author ruochen
 * @version 1.0
 */
public class Loading {
	/** 集装箱数 */
	static int n;
	/** 集装箱重量数组 */
	static int[] w;
	/** 第一艘轮船的载重量 */
	static int c1;
	/** 第二艘轮船的载重量 */
	static int c2;
	/** 当前载重量 */
	static int cw;
	/** 当前最优载重量 */
	static int bestw;
	/** 剩余集装箱重量 */
	static int r;
	/** 当前解 */
	static int[] x;
	/** 当前最优解 */
	static int[] bestx;

	public static void main(String[] args) {
		// 下标从1开始,所以第一个元素为0
		int[] ww = {0, 10, 40, 40};
		int cc1 = 50;
		int cc2 = 50;
		System.out.println(maxLoading(ww, cc1, cc2));
		outPut();
	} /** 返回不超过c 的最大子集和 */
	public static int maxLoading(int[] ww, int cc1, int cc2) {
		n = ww.length - 1;
		w = ww;
		c1 = cc1;
		c2 = cc2;
		cw = 0;
		bestw = 0;
		x = new int[n + 1];
		bestx = new int[n + 1];
		r = 0;
		// r 初始值为全部集装箱总重
		for (int i= 1; i <= n; i++) { r += w[i];
		}
		// 计算最优载重量
		backTrack(1);
		return bestw;
	}

	/** 回溯算法 */
	public static void backTrack(int i) {
		// 搜索第 i 层节点
		if (i > n) { // 到达叶节点 if (cw > bestw) { for (int j = 1; j <= n; j++) { bestx[j] = x[j]; } bestw = cw; } return ;
		}
		// 搜索子树
		r -= w[i];
		if (cw + w[i] <= c1) { // 重量不超过 c // 搜索左子树 x[i] = 1; cw += w[i]; backTrack(i + 1); // 还原 x[i] = 1; cw -= w[i];
		}
		// 只在右子树进行上界函数判断是因为其对左子树无影响
		// 左子树是选择放,上界函数 = cw(当前重量) + r(剩余重量)
		if (cw + r > bestw) { x[i] = 0; // 搜素右子树 backTrack(i + 1);
		}
		r += w[i];
	} static void outPut() {
		int weight = 0;
		for (int i = 1; i <= n; i++) { if (bestx[i] == 0) { // 第一艘轮船装完后的剩余重量 weight += w[i]; }
		}
		if (weight > c2) { System.out.println("不能装入 ");
		} else { System.out.print("轮船一装入的货物为: "); for (int i = 1; i <= n; i++) { if (bestx[i] == 1) { System.out.print(i + " "); } } System.out.println(); System.out.print("轮船二装入的货物为: "); for (int i = 1; i <= n; i++) { if (bestx[i] != 1) { System.out.print(i + " "); } }
		}
	}

}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
50
轮船一装入的货物为: 1 2 
轮船二装入的货物为: 3 

  
 
  • 1
  • 2
  • 3

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

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

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

评论(0

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

全部回复

上滑加载中

设置昵称

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

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

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