贪心算法的应用

仓库管理系统-需要做一个自动匹配云仓格子功能：
要求：质检之后，这一批货黄金首饰的数量quantity为传入参数，返回结果是分配的格子List。

第一期逻辑（2025-10-08）， 先使用 已使用的盘子-格子（如果格子不满则填满），再使用空盘。顺序按创建时间正序（id 正序）排序。
如果已使用的盘子和空胖子两者都没有多的容量，则提示："仓库库存不足，请联系仓库人员"。

第一期业务逻辑简单，优点：分配规则简单，实现简单。缺点：格子可能比较散，拆包数量比较多。

第二期逻辑（2025-12-01）第一期的基础上：现在要求改成 如果quantity数量超过整盘的格子数量（capacity）。则拆分成 quantity=n*capacity+x。

1）参数n为整包，优先使用-已使用的盘子中的格子为空的。如果没有空的格子。则使用空盘的格子。如果两者都没有空的格子则提示："仓库库存不足，请联系仓库人员"

2）参数x为散装数量，和之前逻辑保持一直，优先使用已使用的盘子，如果格子不满则填满，再使用空盘。如果两者都填满，则提示："仓库库存不足，请联系仓库人员"

第三期逻辑扩展逻辑：

3）第二期的基础上：参数x为散装数量，优先使用已使用的盘子，
如果已使用的盘子不满，则获取最可能一次性装满的盘子进行分配（这里使用贪心算法）。
如果没有已使用的盘子，则使用空盘。如果两者都填满，则提示："仓库库存不足，请联系仓库人员"。

核心数据结构定义（格子 / 盘子模型）

java

运行

import lombok.Data; import java.util.ArrayList; import java.util.Comparator; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.stream.Collectors; /** * 云仓格子实体（核心属性） */ @Data public class Grid { // 基础属性 private Long id; // 格子ID（创建时间正序=ID正序） private Long plateId; // 所属盘子ID private Integer capacity; // 格子总容量（比如每个格子固定装10件） private Integer used; // 已使用数量 private Boolean isEmptyPlate; // 是否空盘格子（used=0） // 衍生属性（计算剩余容量） public Integer getRemaining() { return capacity - used; } // 构造函数 public Grid(Long id, Long plateId, Integer capacity, Integer used) { this.id = id; this.plateId = plateId; this.capacity = capacity; this.used = used; this.isEmptyPlate = used == 0; } } /** * 云仓格子分配服务（含第三期贪心算法，返回值调整为List<Map<数量,格子id>>） */ public class GridAllocationService { // 全局配置：单个格子容量（可配置化） private static final Integer GRID_CAPACITY = 10; /** * 核心方法：分配格子（支持整包n+散装x，第三期逻辑） * @param totalQuantity 总数量（传入参数） * @param allGrids 仓库所有格子列表（从DB查询，已按id正序排序） * @return 分配结果：List<Map<分配数量, 格子ID>>；库存不足返回null */ public List<Map<Integer, Long>> allocateGrids(Integer totalQuantity, List<Grid> allGrids) { // 步骤1：拆分整包n和散装x int n = totalQuantity / GRID_CAPACITY; // 整包数量 int x = totalQuantity % GRID_CAPACITY; // 散装数量 if (x == 0) { x = GRID_CAPACITY; // 刚好整包时，x=单格容量，n-1 n -= 1; } // 步骤2：处理整包n（第二期逻辑） List<Grid> packGrids = allocatePackGrids(n, allGrids); if (packGrids == null) { return null; // 库存不足，返回null } // 步骤3：处理散装x（第三期贪心算法核心） List<Grid> bulkGrids = allocateBulkGridsByGreedy(x, allGrids, packGrids); if (bulkGrids == null) { return null; // 库存不足，返回null } // 步骤4：构造返回结果（List<Map<数量, 格子ID>>） List<Map<Integer, Long>> resultList = new ArrayList<>(); // 整包格子：每个分配GRID_CAPACITY数量 for (Grid packGrid : packGrids) { Map<Integer, Long> packMap = new HashMap<>(); packMap.put(GRID_CAPACITY, packGrid.getId()); resultList.add(packMap); } // 散装格子：分配x数量 for (Grid bulkGrid : bulkGrids) { Map<Integer, Long> bulkMap = new HashMap<>(); bulkMap.put(x, bulkGrid.getId()); resultList.add(bulkMap); } return resultList; } /** * 整包n分配（第二期逻辑：优先已使用盘子的空格子→空盘） */ private List<Grid> allocatePackGrids(Integer n, List<Grid> allGrids) { // 筛选：已使用盘子的空格子（used=0，所属盘子有其他格子used>0） List<Grid> usedPlateEmptyGrids = allGrids.stream() .filter(grid -> grid.getUsed() == 0 && isPlateUsed(grid.getPlateId(), allGrids)) .sorted(Comparator.comparing(Grid::getId)) .collect(Collectors.toList()); // 补充：纯空盘格子 List<Grid> emptyPlateGrids = allGrids.stream() .filter(grid -> grid.getUsed() == 0 && !isPlateUsed(grid.getPlateId(), allGrids)) .sorted(Comparator.comparing(Grid::getId)) .collect(Collectors.toList()); // 合并可用整包格子 List<Grid> availablePackGrids = new ArrayList<>(); availablePackGrids.addAll(usedPlateEmptyGrids); availablePackGrids.addAll(emptyPlateGrids); // 检查容量 if (availablePackGrids.size() < n) { return null; } // 取前n个整包格子 return availablePackGrids.subList(0, n); } /** * 散装x分配（第三期贪心算法核心） */ private List<Grid> allocateBulkGridsByGreedy(Integer x, List<Grid> allGrids, List<Grid> usedPackGrids) { // 步骤1：筛选已使用但未装满的格子（排除已分配的整包格子） List<Grid> usedUnfullGrids = allGrids.stream() .filter(grid -> grid.getUsed() > 0 && grid.getRemaining() > 0) .filter(grid -> !usedPackGrids.contains(grid)) // 排除已分配的整包格子 .sorted(Comparator.comparing(Grid::getId)) // 基础规则：id正序 .collect(Collectors.toList()); // 步骤2：贪心选择已使用格子 Grid selectedGrid = null; if (!usedUnfullGrids.isEmpty()) { // 优先级1：找剩余容量≥x 且剩余容量最小的格子 List<Grid> candidate1 = usedUnfullGrids.stream() .filter(grid -> grid.getRemaining() >= x) .sorted(Comparator.comparing(Grid::getRemaining)) // 剩余容量升序→选最小的 .collect(Collectors.toList()); if (!candidate1.isEmpty()) { selectedGrid = candidate1.get(0); // 选第一个（最小剩余容量） } else { // 优先级2：找剩余容量最大的已使用格子 selectedGrid = usedUnfullGrids.stream() .max(Comparator.comparing(Grid::getRemaining)) .orElse(null); } } // 步骤3：若无已使用格子，选空盘格子（排除已分配的整包格子） if (selectedGrid == null) { List<Grid> emptyGrids = allGrids.stream() .filter(grid -> grid.getUsed() == 0) .filter(grid -> !usedPackGrids.contains(grid)) .sorted(Comparator.comparing(Grid::getId)) .collect(Collectors.toList()); if (emptyGrids.isEmpty()) { return null; // 无空盘格子，库存不足 } selectedGrid = emptyGrids.get(0); } // 步骤4：检查选中格子的剩余容量是否足够（不足则库存不足） if (selectedGrid.getRemaining() < x) { return null; } // 步骤5：返回分配结果 List<Grid> result = new ArrayList<>(); result.add(selectedGrid); return result; } /** * 辅助方法：判断盘子是否为已使用盘子（有格子被使用） */ private boolean isPlateUsed(Long plateId, List<Grid> allGrids) { return allGrids.stream() .filter(grid -> grid.getPlateId().equals(plateId)) .anyMatch(grid -> grid.getUsed() > 0); } // 测试用例 public static void main(String[] args) { GridAllocationService service = new GridAllocationService(); // 模拟仓库格子数据（id正序=创建时间正序） List<Grid> allGrids = new ArrayList<>(); allGrids.add(new Grid(1L, 101L, 10, 8)); // 已使用，剩余2 allGrids.add(new Grid(2L, 101L, 10, 5)); // 已使用，剩余5 allGrids.add(new Grid(3L, 102L, 10, 0)); // 空盘格子 allGrids.add(new Grid(4L, 101L, 10, 3)); // 已使用，剩余7 allGrids.add(new Grid(5L, 103L, 10, 0)); // 空盘格子 // 测试场景：总数量=27 → n=2（2*10），x=7 List<Map<Integer, Long>> result = service.allocateGrids(27, allGrids); if (result == null) { System.out.println("仓库库存不足，请联系仓库人员"); } else { System.out.println("分配成功，分配结果："); for (Map<Integer, Long> map : result) { // 遍历Map（每个Map只有一个键值对：数量→格子ID） map.forEach((quantity, gridId) -> System.out.println("格子ID：" + gridId + "，分配数量：" + quantity) ); } } // 预期输出： // 格子ID：3，分配数量：10 // 格子ID：5，分配数量：10 // 格子ID：4，分配数量：7 } }

2. 代码关键说明

表格

总结

1. 核心返回结构：List<Map<Integer, Long>>中每个 Map 仅包含一个键值对（分配数量→格子 ID），符合 “一个格子对应一个分配数量” 的业务逻辑；
2. 贪心算法保留：散装分配的贪心策略（优先最小剩余≥x→最大剩余）完全保留，仅调整返回值格式；
3. 边界处理：库存不足返回null，外层可根据null判断输出标准化提示；
4. 测试验证：新增的测试用例可直接运行，验证返回结果的正确性。