三维装箱问题Java源码

Colin 1年前 ⋅ 2672 阅读

之前在CSDN上公布一篇《三维装箱问题Java代码的简单实现过程》,应诸多网友的强烈要求,现将代码公布在我的博客上。一共四个文件,第一个文件是主类负责主要的业务逻辑,其它三个文件均围绕第一个类所做的测试类。代码对应的实现思路请参考CSDN的一篇文章: https://blog.csdn.net/chun0/article/details/51837191 ,代码如下(文章结尾处可打包下载): 

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author colin
 *
 */
public class GoodsInBox {

	/* 箱子的型号,盛放空间 */
	private List<Map<String, Object>> boxTypeList;
	/* 订单中的商品 */
	private List<Map<String, Object>> goodsList;
	/* 箱子装东西的情况,key 规则:箱型_箱子id */
	private Map<Object, Object> boxes = new HashMap<Object, Object>();

	/*-
	 * 根据箱型以及订单中的商品,返回每个箱型需要箱子多少只。如果没有任何的箱子能装下某一款超大商品的时候,抛出异常       
	 * @param linkedHashMap
	 * @param orderItemArr
	 * @return     
	 */
	public GoodsInBox(List<Map<String, Object>> boxTypeList, List<Map<String, Object>> goodsList) {
		this.boxTypeList = boxTypeList;
		this.goodsList = goodsList;
		// 开始执行
		run();
	}

	// 执行装箱
	@SuppressWarnings("serial")
	private void run() {
		// 预先跑一遍看看,有没有特别大的东西
		double gl = 0d, gw = 0d, gh = 0d;
		double bl = 0d, bw = 0d, bh = 0d;
		int num = 0;
		for (Map<String, Object> g : goodsList) {
			num += Integer.valueOf(g.get("n").toString());
			gl = Double.max(gl, Double.valueOf(g.get("l").toString()));
			gw = Double.max(gw, Double.valueOf(g.get("w").toString()));
			gh = Double.max(gh, Double.valueOf(g.get("h").toString()));
		}
		for (Map<String, Object> b : boxTypeList) {
			bl = Double.max(bl, Double.valueOf(b.get("l").toString()));
			bw = Double.max(bw, Double.valueOf(b.get("w").toString()));
			bh = Double.max(bh, Double.valueOf(b.get("h").toString()));
		}
		if (gl > bl && gl > bw) {
			throw new java.lang.RuntimeException("估算失败,存在体积过大商品,请重新选择后再试。(长度超出范围)");
		}
		if (gw > bw && gw > bl) {
			throw new java.lang.RuntimeException("估算失败,存在体积过大商品,请重新选择后再试。(宽度超出范围)");
		}
		if (gh > bh) {
			throw new java.lang.RuntimeException("估算失败,存在体积过大商品,请重新选择后再试。(高度超出范围)");
		}
		if (num > 500) {
			throw new java.lang.RuntimeException("估算失败,商品数量过多,请重新选择后再试。(大于500件)");
		}

		for (final Map<String, Object> abox : boxTypeList) {
			tryInSpance(abox/* 给一个盒子 */, new java.util.ArrayList<Map<String, Object>>() {
				{
					this.add(abox);
				}
			}/* 什么都没有装,盒子的空间还是这个盒子 */, false/* 已知目前这个盒子没有满 */, (goodsList)/* 急需进入盒子的商品 */, boxTypeList);
		}
	}

	/*-
	 * 每次测试1块空间,和全部商品,将商品依次向空间转移,放进去后产生新的3块空间, 同时商品的数量再减少,直到商品全部转移;     
	 * @param space1
	 * @param gs
	 * @return     
	 */
	@SuppressWarnings("unused")
	private List<Map<String, Object>>/* 尝试装一件商品后返回剩下的三块空间 */ tryInSpance(
			Map<String/* 长l宽w高h等 */, Object> box/* 某1个盒子 */, List<Map<String, Object>> moreSpance/* 某一个盒子的剩余空间 */,
			boolean boxIsFull, List<Map<String, Object>> moreGoods, List<Map<String, Object>> boxTypes /* 可用的箱子型号 */) {
		// 为新的箱子分配一个箱子的唯一id,箱子型號+uuid保證每一個箱子的id唯一。箱子被裝滿之後,箱子的屬性為滿。
		// 如果没有boxid表示是一个新的箱子
		// 如果之前的箱子满了也需要新的箱子
		if (null == box.get("boxid") || boxIsFull) {
			box.put("boxid", box.get("id").toString().concat("_").concat(java.util.UUID.randomUUID().toString()));
			moreSpance = new java.util.ArrayList<Map<String, Object>>();
			moreSpance.add(box);
		}

		if (null == box || null == moreGoods || null == moreSpance)
			return null;
		// 是否有东西被装进去?
		boolean in = false;
		// 遍历这个箱子的剩余空间;
		loops: for (int bi = moreSpance.size() - 1; bi >= 0; bi--) {
			Map<String, Object> b = moreSpance.get(bi);
			if (null == b) {
				continue loops;
			}
			double bl = Double.valueOf(b.get("l").toString());
			double bw = Double.valueOf(b.get("w").toString());
			double bh = Double.valueOf(b.get("h").toString());

			if (bl <= 0 || bw <= 0 || bh <= 0)
				continue;

			// 遍历未装箱的商品列表
			loopg: for (int gi = moreGoods.size() - 1; gi >= 0; gi--) {
				Map<String, Object> g = moreGoods.get(gi);
				if (null == g.get("n") || null == g.get("sku"))
					continue;
				Integer sku = Integer.valueOf(g.get("sku").toString());
				// 商品数量
				Integer num = Integer.valueOf(g.get("n").toString());
				if (0 == num) {
					moreGoods.remove(gi);
					// 继续下一个商品
					continue loopg;
				}
				// boolean goodsinbox = false;
				// 多少件商品就循环多少次,每次处理一件;
				loopn: for (int i = num; i >= 0; i--) {
					String code = box.get("code").toString().concat(",").concat(sku.toString());
					double gl = Double.valueOf(g.get("l").toString());
					double gw = Double.valueOf(g.get("w").toString());
					double gh = Double.valueOf(g.get("h").toString());
					Integer t = Integer.valueOf(g.get("t").toString()); // 0,可平躺可码放不可倒置;1,不可平躺可码放不可倒置;2,不可平躺不可码放不可倒置

					// 正面放置商品
					if ((bl - gl) >= 0d && (bw - gw) >= 0d && (bh - gh) >= 0d) {
						// 这件商品被装进了这个盒子;是正着被放进去的。
						g.put("boxid", box.get("boxid"));
						// 商品的数量要减少一个
						g.put("n", i - 1);
						// 剩余空间需要减少一个
						moreSpance.remove(bi);
						in = true;
						boxes.put(box.get("boxid"), g);

						// 正放的3块剩余空间
						if (2 != t.intValue() && bh - gh > 0d) {
							Map<String, Object> leftover;
							// 第一块空间 (盒子上面的剩余空间) bh - gh 高度相减表示盒子正上方
							leftover = new HashMap<String, Object>();
							leftover.put("boxid", box.get("boxid"));
							leftover.put("id", box.get("id"));
							leftover.put("l", gl);
							leftover.put("w", gw);
							leftover.put("h", bh - gh);
							leftover.put("code", code);
							moreSpance.add(leftover);
						}
						// 第二块空间
						if (bw - gw > 0d) {
							Map<String, Object> leftover;
							leftover = new HashMap<String, Object>();
							leftover.put("boxid", box.get("boxid"));
							leftover.put("id", box.get("id"));

							leftover.put("l", gl);
							leftover.put("w", bw - gw);
							leftover.put("h", bh);
							leftover.put("code", code);
							moreSpance.add(leftover);

						}
						// 第三块空间
						if (bl - gl > 0d) {
							Map<String, Object> leftover;
							leftover = new HashMap<String, Object>();
							leftover.put("boxid", box.get("boxid"));
							leftover.put("id", box.get("id"));

							leftover.put("l", bl - gl);
							leftover.put("w", bw);
							leftover.put("h", bh);
							leftover.put("code", code);
							moreSpance.add(leftover);
						}

						tryInSpance(box, moreSpance, moreSpance.isEmpty() ? true : false, moreGoods, boxTypes);
						return moreSpance;

						// 侧面放置商品
					} else if ((bl - gw) >= 0d && (bw - gl) >= 0d && (bh - gh) >= 0d) {
						// 可以放入的情况下先减少商品的数量;
						// 这件商品被装进了这个盒子;
						g.put("boxid", box.get("boxid"));
						// 商品的数量要减少一个
						g.put("n", i - 1);
						// 剩余空间需要减少一个
						moreSpance.remove(bi);
						in = true;
						boxes.put(box.get("boxid"), g);
						// 侧放的3块剩余空间
						if (2 != t.intValue() && bh - gh > 0d) {
							Map<String, Object> leftover;
							// 第一块空间
							leftover = new HashMap<String, Object>();
							leftover.put("boxid", box.get("boxid"));
							leftover.put("id", box.get("id"));

							leftover.put("l", gl);
							leftover.put("w", gw);
							leftover.put("h", bh - gh);
							leftover.put("code", code);
							moreSpance.add(leftover);
						}
						// 第二块空间
						if (bw - gl > 0d) {
							Map<String, Object> leftover;
							leftover = new HashMap<String, Object>();
							leftover.put("boxid", box.get("boxid"));
							leftover.put("id", box.get("id"));

							leftover.put("l", bw - gl);
							leftover.put("w", gw);
							leftover.put("h", bh);
							leftover.put("code", code);
							moreSpance.add(leftover);
						}
						// 第三块空间
						if (bl - gw > 0d) {
							Map<String, Object> leftover;
							leftover = new HashMap<String, Object>();
							leftover.put("boxid", box.get("boxid"));
							leftover.put("id", box.get("id"));

							leftover.put("l", bl - gw);
							leftover.put("w", bw);
							leftover.put("h", bh);
							leftover.put("code", code);
							moreSpance.add(leftover);
						}

						tryInSpance(box, moreSpance, moreSpance.isEmpty() ? true : false, moreGoods, boxTypes);
						return moreSpance;

						// 卧倒放置商品
					} else if (t.intValue() == 0d && (bl - gh) >= 0d && (bw - gw) >= 0d && (bw - gl) >= 0d) {
						// 这件商品被装进了这个盒子;
						g.put("boxid", box.get("boxid"));
						// 商品的数量要减少一个
						g.put("n", i - 1);
						// 剩余空间需要减少一个
						moreSpance.remove(bi);
						in = true;
						boxes.put(box.get("boxid"), g);
						// 侧放的3块剩余空间

						if (2 != t.intValue() && bh - gh > 0d) {
							// 第一块空间
							Map<String, Object> leftover;
							leftover = new HashMap<String, Object>();
							leftover.put("boxid", box.get("boxid"));
							leftover.put("id", box.get("id"));

							leftover.put("l", gh);
							leftover.put("w", gw);
							leftover.put("h", bh - gh);
							leftover.put("code", code);
							moreSpance.add(leftover);
						}
						// 第二块空间
						if (bw - gw > 0d) {
							Map<String, Object> leftover;
							leftover = new HashMap<String, Object>();
							leftover.put("boxid", box.get("boxid"));
							leftover.put("id", box.get("id"));

							leftover.put("l", bw - gw);
							leftover.put("w", gh);
							leftover.put("h", bh);
							leftover.put("code", code);
							moreSpance.add(leftover);
						}
						// 第三块空间
						if (bl - gh > 0d) {
							Map<String, Object> leftover;
							leftover = new HashMap<String, Object>();
							leftover.put("boxid", box.get("boxid"));
							leftover.put("id", box.get("id"));

							leftover.put("l", bl - gh);
							leftover.put("w", bw);
							leftover.put("h", bh);
							leftover.put("code", code);
							moreSpance.add(leftover);
						}

						tryInSpance(box, moreSpance, moreSpance.isEmpty() ? true : false, moreGoods, boxTypes);
						return moreSpance;
						// 侧卧放置商品
					} else if (t.intValue() == 0d && (bl - gw) >= 0d && (bh - gl) >= 0d && (bw - gh) >= 0d) {
						// 这件商品被装进了这个盒子;
						g.put("boxid", box.get("boxid"));
						// 商品的数量要减少一个
						g.put("n", i - 1);
						// 剩余空间需要减少一个
						moreSpance.remove(bi);
						in = true;
						boxes.put(box.get("boxid"), g);
						// 侧放的3块剩余空间

						if (2 != t.intValue() && bh - gl > 0d) {
							Map<String, Object> leftover;
							// 第一块空间
							leftover = new HashMap<String, Object>();
							leftover.put("boxid", box.get("boxid"));
							leftover.put("id", box.get("id"));

							leftover.put("l", gw);
							leftover.put("w", gh);
							leftover.put("h", bh - gl);
							leftover.put("code", code);
							moreSpance.add(leftover);
						}
						// 第二块空间
						if (bw - gh > 0d) {
							Map<String, Object> leftover;
							leftover = new HashMap<String, Object>();
							leftover.put("boxid", box.get("boxid"));
							leftover.put("id", box.get("id"));

							leftover.put("l", bw - gh);
							leftover.put("w", gw);
							leftover.put("h", bh);
							leftover.put("code", code);
							moreSpance.add(leftover);
						}
						// 第三块空间
						if (bl - gw > 0d) {
							Map<String, Object> leftover;
							leftover = new HashMap<String, Object>();
							leftover.put("boxid", box.get("boxid"));
							leftover.put("id", box.get("id"));

							leftover.put("l", bl - gw);
							leftover.put("w", bw);
							leftover.put("h", bh);
							leftover.put("code", code);
							moreSpance.add(leftover);
						}

						tryInSpance(box, moreSpance, moreSpance.isEmpty() ? true : false, moreGoods, boxTypes);
						return moreSpance;
					}
				}
			}

		}
		// 任何东西都装不下了
		if (!in)
			box.put("boxid", box.get("id").toString().concat("_").concat(java.util.UUID.randomUUID().toString()));
		return null;
	}

	public Map<String, Integer> getBoxes() {
		Map<String, Integer> boxNum = new HashMap<String, Integer>();
		for (Object k : boxes.keySet()) {
			String boxid = k.toString().split("_")[0];
			Integer count = 1;
			if (boxNum.get(boxid) != null)
				count = boxNum.get(boxid) + 1;
			boxNum.put(boxid, count);
		}
		return boxNum;
	}

}

 

测试代码如下:

 

1,测试用例:两款包装盒,订单商品1件,体积1立方米

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TestOrder1Box {

	@SuppressWarnings("serial")
	public static void main(String[] args) {

		// 假设仓库有两款箱子(谁排前面优先用谁)
		List<Map<String, Object>> boxes = new ArrayList<Map<String, Object>>() {
			{
				
				// 盒子 1x1x1
				this.add(new HashMap<String, Object>() {
					{

						this.put("id", "1");// 盒子ID
						this.put("code", "1");// 盒子CODE
						this.put("title", "1立方的盒子");// 盒子名称
						this.put("l", 100.00d); // 盒子高度
						this.put("w", 100.00d);// 盒子宽度
						this.put("h", 100.00d);// 盒子高度
					}
				});

				// 盒子 1x1x2
				this.add(new HashMap<String, Object>() {
					{

						this.put("id", "2");// 盒子ID
						this.put("code", "2");// 盒子CODE
						this.put("title", "2立方的盒子");// 盒子名称
						this.put("l", 100.00d); // 盒子高度
						this.put("w", 100.00d);// 盒子宽度
						this.put("h", 200.00d);// 盒子高度
					}
				});

			
			}

		};

		// 订单中的商品列表
		List<Map<String, Object>> order = new ArrayList<Map<String, Object>>() {
			{
				// 商品也是1立方,1x1x1
				this.add(new HashMap<String, Object>() {
					{
						this.put("sku", "222");// 商品SKUID
						this.put("title", "1立方商品2件");// 商品名称
						this.put("l", 100.00d); // 商品长度
						this.put("w", 100.00d); // 商品宽度
						this.put("h", 100.00d); // 商品高度
						this.put("n", 1); // 该商品数量
						this.put("t", 1);// 0,可平躺可码放不可倒置;1,不可平躺可码放不可倒置;2,不可平躺不可码放不可倒置
					}
				});
			}
		};

		// 将商品装入盒中
		GoodsInBox gb = new GoodsInBox(boxes, order);

		// 得到需要盒子的数量
		Map<String, Integer> boxInfo = gb.getBoxes();
		for (Object k : boxInfo.keySet()) {
			System.out.print("该订单商品需要");
			System.out.print(k.toString());
			System.out.print("(ID)号箱:");
			System.out.print(boxInfo.get(k));
			System.out.print("只。");
		}

	}

}

 

测试结果:

该订单商品需要1(ID)号箱:1只。

 

2,测试用例:两款包装盒,订单商品2件,每件体积1立方米

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TestOrder2Box {
	@SuppressWarnings("serial")
	public static void main(String[] args) {

		// 假设仓库有两款箱子(谁排前面优先用谁)
		List<Map<String, Object>> boxes = new ArrayList<Map<String, Object>>() {
			{

				// 盒子 1x1x1
				this.add(new HashMap<String, Object>() {
					{

						this.put("id", "1");// 盒子ID
						this.put("code", "1");// 盒子CODE
						this.put("title", "1立方的盒子");// 盒子名称
						this.put("l", 100.00d); // 盒子高度
						this.put("w", 100.00d);// 盒子宽度
						this.put("h", 100.00d);// 盒子高度
					}
				});

				// 盒子 1x1x2
				this.add(new HashMap<String, Object>() {
					{

						this.put("id", "2");// 盒子ID
						this.put("code", "2");// 盒子CODE
						this.put("title", "2立方的盒子");// 盒子名称
						this.put("l", 100.00d); // 盒子高度
						this.put("w", 100.00d);// 盒子宽度
						this.put("h", 200.00d);// 盒子高度
					}
				});

			}

		};

		// 订单中的商品列表
		List<Map<String, Object>> order = new ArrayList<Map<String, Object>>() {
			{
				// 商品也是1立方,1x1x1
				this.add(new HashMap<String, Object>() {
					{
						this.put("sku", "222");// 商品SKUID
						this.put("title", "1立方商品2件");// 商品名称
						this.put("l", 100.00d); // 商品长度
						this.put("w", 100.00d); // 商品宽度
						this.put("h", 100.00d); // 商品高度
						this.put("n", 2); // 该商品数量
						this.put("t", 1);// 0,可平躺可码放不可倒置;1,不可平躺可码放不可倒置;2,不可平躺不可码放不可倒置
					}
				});
			}
		};

		// 将商品装入盒中
		GoodsInBox gb = new GoodsInBox(boxes, order);

		// 得到需要盒子的数量
		Map<String, Integer> boxInfo = gb.getBoxes();
		for (Object k : boxInfo.keySet()) {
			System.out.print("该订单商品需要");
			System.out.print(k.toString());
			System.out.print("(ID)号箱:");
			System.out.print(boxInfo.get(k));
			System.out.print("只。");
		}

	}

}

 

测试结果:

该订单商品需要1(ID)号箱:2只。

 

3,测试用例:两款包装盒,订单商品2件,每件体积2立方米

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TestOrder3Box {
	@SuppressWarnings("serial")
	public static void main(String[] args) {

		// 假设仓库有两款箱子(谁排前面优先用谁)
		List<Map<String, Object>> boxes = new ArrayList<Map<String, Object>>() {
			{

				// 盒子 1x1x1
				this.add(new HashMap<String, Object>() {
					{

						this.put("id", "1");// 盒子ID
						this.put("code", "1");// 盒子CODE
						this.put("title", "1立方的盒子");// 盒子名称
						this.put("l", 100.00d); // 盒子高度
						this.put("w", 100.00d);// 盒子宽度
						this.put("h", 100.00d);// 盒子高度
					}
				});

				// 盒子 1x1x2
				this.add(new HashMap<String, Object>() {
					{

						this.put("id", "2");// 盒子ID
						this.put("code", "2");// 盒子CODE
						this.put("title", "2立方的盒子");// 盒子名称
						this.put("l", 100.00d); // 盒子高度
						this.put("w", 100.00d);// 盒子宽度
						this.put("h", 200.00d);// 盒子高度
					}
				});

			}

		};

		// 订单中的商品列表
		List<Map<String, Object>> order = new ArrayList<Map<String, Object>>() {
			{
				// 商品也是1立方,1x1x1
				this.add(new HashMap<String, Object>() {
					{
						this.put("sku", "222");// 商品SKUID
						this.put("title", "1立方商品2件");// 商品名称
						this.put("l", 100.00d); // 商品长度
						this.put("w", 100.00d); // 商品宽度
						this.put("h", 200.00d); // 商品高度
						this.put("n", 2); // 该商品数量
						this.put("t", 1);// 0,可平躺可码放不可倒置;1,不可平躺可码放不可倒置;2,不可平躺不可码放不可倒置
					}
				});
			}
		};

		// 将商品装入盒中
		GoodsInBox gb = new GoodsInBox(boxes, order);

		// 得到需要盒子的数量
		Map<String, Integer> boxInfo = gb.getBoxes();
		for (Object k : boxInfo.keySet()) {
			System.out.print("该订单商品需要");
			System.out.print(k.toString());
			System.out.print("(ID)号箱:");
			System.out.print(boxInfo.get(k));
			System.out.print("只。");
		}

	}

}

测试结果:

该订单商品需要2(ID)号箱:2只。

 

还可以根据上述测试用例自行组织数据测试主类。以上代码仅通过简单测试,并未经历实际生产或极端测试。遇到问题请自行调整代码逻辑,同时也欢迎留言留下您的建议和看法。

登陆之后点击此链接可下载源代码

 

全部评论: 0

    我有话说: