import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
public class LocationAllocator {
private static final Pattern LOC_PATTERN = Pattern.compile("^(L\\d+)-(\\d+)$");
private static final int MIN_SLOT = 1;
private static final int MAX_SLOT = 25;
private static final int MAX_ROWS_PER_LOT = 3;
/** lotid -> 分到的库位列表 */
public Map<String, List<String>> allocate(List<String> locations, List<LabSampleInoutVo> list) {
// 1. 解析并按行分组，行内按槽位排序
Map<String, List<Slot>> rowMap = groupAvailable(locations);
// 行顺序：L1, L2, L3 ...（按行号数字，不是字符串）
List<String> rowKeys = new ArrayList<>(rowMap.keySet());
rowKeys.sort(Comparator.comparingInt(this::rowNumber));
// 2. 同一 lotid 数量合并，再按 quantity 升序
List<LotNeed> needs = mergeAndSort(list);
Map<String, List<String>> result = new LinkedHashMap<>();
for (LotNeed need : needs) {
List<String> chosenRows = findRows(rowKeys, rowMap, need.quantity);
if (chosenRows == null) {
throw new IllegalStateException(
"无法为 lotid=" + need.lotid + " 分配 " + need.quantity
+ " 个位置（最多组合 " + MAX_ROWS_PER_LOT + " 行）");
}
List<String> assigned = takeSlots(rowMap, chosenRows, need.quantity);
result.put(need.lotid, assigned);
}
return result;
}
private Map<String, List<Slot>> groupAvailable(List<String> locations) {
Map<String, List<Slot>> map = new LinkedHashMap<>();
if (locations == null) {
return map;
}
for (String loc : locations) {
if (loc == null) {
continue;
}
Matcher m = LOC_PATTERN.matcher(loc.trim());
if (!m.matches()) {
continue;
}
String row = m.group(1); // L1
int slot = Integer.parseInt(m.group(2));
if (slot < MIN_SLOT || slot > MAX_SLOT) {
continue;
}
map.computeIfAbsent(row, k -> new ArrayList<>()).add(new Slot(loc.trim(), slot));
}
for (List<Slot> slots : map.values()) {
slots.sort(Comparator.comparingInt(s -> s.slot));
}
return map;
}
private List<LotNeed> mergeAndSort(List<LabSampleInoutVo> list) {
Map<String, Integer> qtyByLot = new LinkedHashMap<>();
for (LabSampleInoutVo vo : list) {
if (vo == null || vo.getLotid() == null || vo.getQuantity() == null) {
continue;
}
qtyByLot.merge(vo.getLotid(), vo.getQuantity(), Integer::sum);
}
return qtyByLot.entrySet().stream()
.map(e -> new LotNeed(e.getKey(), e.getValue()))
.sorted(Comparator.comparingInt((LotNeed n) -> n.quantity)
.thenComparing(n -> n.lotid))
.collect(Collectors.toList());
}
/** 先 1 行，再 2 行，再 3 行；同层按行号组合顺序，找到第一个剩余之和 >= quantity */
private List<String> findRows(List<String> rowKeys, Map<String, List<Slot>> rowMap, int quantity) {
int n = rowKeys.size();
for (int k = 1; k <= MAX_ROWS_PER_LOT; k++) {
List<Integer> idx = new ArrayList<>();
List<String> found = new ArrayList<>();
if (dfsCombine(rowKeys, rowMap, quantity, k, 0, idx, found)) {
return found;
}
}
return null;
}
private boolean dfsCombine(List<String> rowKeys, Map<String, List<Slot>> rowMap,
int quantity, int k, int start,
List<Integer> idx, List<String> out) {
if (idx.size() == k) {
int sum = 0;
for (int i : idx) {
sum += remaining(rowMap, rowKeys.get(i));
}
if (sum >= quantity) {
out.clear();
for (int i : idx) {
out.add(rowKeys.get(i));
}
return true;
}
return false;
}
for (int i = start; i < rowKeys.size(); i++) {
if (remaining(rowMap, rowKeys.get(i)) <= 0) {
continue;
}
idx.add(i);
if (dfsCombine(rowKeys, rowMap, quantity, k, i + 1, idx, out)) {
return true;
}
idx.remove(idx.size() - 1);
}
return false;
}
private int remaining(Map<String, List<Slot>> rowMap, String row) {
List<Slot> slots = rowMap.get(row);
return slots == null ? 0 : slots.size();
}
/** 按选中行顺序，每行从左到右（槽位号升序）取走 */
private List<String> takeSlots(Map<String, List<Slot>> rowMap, List<String> rows, int quantity) {
List<String> assigned = new ArrayList<>(quantity);
int left = quantity;
for (String row : rows) {
List<Slot> slots = rowMap.get(row);
if (slots == null || slots.isEmpty()) {
continue;
}
int take = Math.min(left, slots.size());
for (int i = 0; i < take; i++) {
assigned.add(slots.get(i).code);
}
slots.subList(0, take).clear();
left -= take;
if (left == 0) {
break;
}
}
return assigned;
}
private int rowNumber(String row) {
return Integer.parseInt(row.substring(1));
}
private static class Slot {
final String code;
final int slot;
Slot(String code, int slot) {
this.code = code;
this.slot = slot;
}
}
private static class LotNeed {
final String lotid;
final int quantity;
LotNeed(String lotid, int quantity) {
this.lotid = lotid;
this.quantity = quantity;
}
}
}
1
public class LabSampleInoutVo {
private String lotid;
private Integer quantity;
public String getLotid() { return lotid; }
public Integer getQuantity() { return quantity; }
}
111
调用：
Map<String, List<String>> assigned = new LocationAllocator().allocate(locations, list);
2
规则理解
这是一个按行（L1、L2…）分组、优先少用行、最多拼 3 行的库位分配问题。当前仓库是 Godot 项目，没有现成 Java 类，下面按你描述的规则给出可直接用的实现。
规则理解
- 只认
L数字-1~25，例如L1-1、L2-25；locations里没有的就是已被占用。- 同一
lotid视为一种，按quantity要几个空位。- 数量少的 lot 先分，避免大单把零散空位占完。
- 按行号分组：
L1剩几个、L2剩几个。- 对某个
quantity = Q：
- 先找一行剩余
>= Q- 没有则两行相加：
L1+L2→L1+L3→ … →L2+L3…- 再没有则三行：
L1+L2+L3…- 三行仍不够就报错
- 一行内按槽位号从小到大取（
L1-1…L1-25中还空着的）。你举例里「只要 1 个时 L1 满足」按第一行剩余 ≥ 需求理解；「L1 还剩唯一空位」是另一种数据下的特例。
对应你的例子
假设剩余：
L1=5, L2=4, L3=3, L4=8
需求 Q 怎么选 1
第一行剩余 ≥ 1 → 用
L1里槽位最小的那个8
单行：
L4正好 ≥ 89
单行都不够 →
L1+L2=9刚好10
L1+L2=9不够 →L1+L3=8不够 →L1+L4=13够20
两行最大
L1+L4=13不够 → 试三行，例如L1+L2+L4=17仍不够则继续，直到某三行之和 ≥ 20；都不行就报错分完一个 lot 后，这些库位会从剩余里删掉，再处理下一个（数量更大的）lot。
需要你确认的两点
- 同一
lotid多条记录：上面是合并 quantity。若每条要单独分配，把mergeAndSort改成不合并即可。- 两行组合顺序：按
L1+L2, L1+L3, …（行号升序组合）。若必须固定「始终以当前最小行号为锚」也可以，当前实现就是这个。如果你把
LabSampleInoutVo真实字段名、以及分配结果要写回哪个字段（例如location）发我，我可以改成贴合你们现有 Service 的版本。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/m0_62474094/article/details/169266985
