贪心算法的应用

仓库管理系统-需要做一个自动匹配云仓格子功能要求质检之后这一批货黄金首饰的数量quantity为传入参数返回结果是分配的格子List。第一期逻辑2025-10-08 先使用 已使用的盘子-格子如果格子不满则填满再使用空盘。顺序按创建时间正序id 正序排序。如果已使用的盘子和空胖子两者都没有多的容量则提示仓库库存不足请联系仓库人员。第一期业务逻辑简单优点分配规则简单实现简单。缺点格子可能比较散拆包数量比较多。第二期逻辑2025-12-01第一期的基础上现在要求改成 如果quantity数量超过整盘的格子数量capacity。则拆分成 quantityn*capacityx。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; // 是否空盘格子used0 // 衍生属性计算剩余容量 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; } } /** * 云仓格子分配服务含第三期贪心算法返回值调整为ListMap数量,格子id */ public class GridAllocationService { // 全局配置单个格子容量可配置化 private static final Integer GRID_CAPACITY 10; /** * 核心方法分配格子支持整包n散装x第三期逻辑 * param totalQuantity 总数量传入参数 * param allGrids 仓库所有格子列表从DB查询已按id正序排序 * return 分配结果ListMap分配数量, 格子ID库存不足返回null */ public ListMapInteger, Long allocateGrids(Integer totalQuantity, ListGrid 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第二期逻辑 ListGrid packGrids allocatePackGrids(n, allGrids); if (packGrids null) { return null; // 库存不足返回null } // 步骤3处理散装x第三期贪心算法核心 ListGrid bulkGrids allocateBulkGridsByGreedy(x, allGrids, packGrids); if (bulkGrids null) { return null; // 库存不足返回null } // 步骤4构造返回结果ListMap数量, 格子ID ListMapInteger, Long resultList new ArrayList(); // 整包格子每个分配GRID_CAPACITY数量 for (Grid packGrid : packGrids) { MapInteger, Long packMap new HashMap(); packMap.put(GRID_CAPACITY, packGrid.getId()); resultList.add(packMap); } // 散装格子分配x数量 for (Grid bulkGrid : bulkGrids) { MapInteger, Long bulkMap new HashMap(); bulkMap.put(x, bulkGrid.getId()); resultList.add(bulkMap); } return resultList; } /** * 整包n分配第二期逻辑优先已使用盘子的空格子→空盘 */ private ListGrid allocatePackGrids(Integer n, ListGrid allGrids) { // 筛选已使用盘子的空格子used0所属盘子有其他格子used0 ListGrid usedPlateEmptyGrids allGrids.stream() .filter(grid - grid.getUsed() 0 isPlateUsed(grid.getPlateId(), allGrids)) .sorted(Comparator.comparing(Grid::getId)) .collect(Collectors.toList()); // 补充纯空盘格子 ListGrid emptyPlateGrids allGrids.stream() .filter(grid - grid.getUsed() 0 !isPlateUsed(grid.getPlateId(), allGrids)) .sorted(Comparator.comparing(Grid::getId)) .collect(Collectors.toList()); // 合并可用整包格子 ListGrid availablePackGrids new ArrayList(); availablePackGrids.addAll(usedPlateEmptyGrids); availablePackGrids.addAll(emptyPlateGrids); // 检查容量 if (availablePackGrids.size() n) { return null; } // 取前n个整包格子 return availablePackGrids.subList(0, n); } /** * 散装x分配第三期贪心算法核心 */ private ListGrid allocateBulkGridsByGreedy(Integer x, ListGrid allGrids, ListGrid usedPackGrids) { // 步骤1筛选已使用但未装满的格子排除已分配的整包格子 ListGrid 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 且剩余容量最小的格子 ListGrid 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) { ListGrid 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返回分配结果 ListGrid result new ArrayList(); result.add(selectedGrid); return result; } /** * 辅助方法判断盘子是否为已使用盘子有格子被使用 */ private boolean isPlateUsed(Long plateId, ListGrid 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正序创建时间正序 ListGrid 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 → n22*10x7 ListMapInteger, Long result service.allocateGrids(27, allGrids); if (result null) { System.out.println(仓库库存不足请联系仓库人员); } else { System.out.println(分配成功分配结果); for (MapInteger, Long map : result) { // 遍历Map每个Map只有一个键值对数量→格子ID map.forEach((quantity, gridId) - System.out.println(格子ID gridId 分配数量 quantity) ); } } // 预期输出 // 格子ID3分配数量10 // 格子ID5分配数量10 // 格子ID4分配数量7 } }2. 代码关键说明表格核心方法作用贪心体现allocateBulkGridsByGreedy散装 x 分配核心1. 优先选 “剩余≥x 且最小” 的格子2. 无则选 “剩余最大” 的格子candidate1筛选优先级 1 选择局部最优最小化空间浪费max(Comparator.comparing(Grid::getRemaining))优先级 2 选择局部最优最大化利用剩余空间减少拆包全程id正序基础规则遵守 “创建时间正序” 的业务要求总结核心返回结构ListMapInteger, Long中每个 Map 仅包含一个键值对分配数量→格子 ID符合 “一个格子对应一个分配数量” 的业务逻辑贪心算法保留散装分配的贪心策略优先最小剩余≥x→最大剩余完全保留仅调整返回值格式边界处理库存不足返回null外层可根据null判断输出标准化提示测试验证新增的测试用例可直接运行验证返回结果的正确性。