package com.zy.asrs.utils;
|
|
import com.core.common.SnowflakeIdWorker;
|
import com.core.common.SpringUtils;
|
|
import java.util.*;
|
|
public class OptimizedLockerPacking3Utils {
|
|
public static class Item {
|
String name;
|
double unitSpace;
|
int maxCapacity;
|
int stock;
|
int allocated; // 改为已分配数量，避免直接修改remaining导致的混乱
|
|
public Item(String name, int maxCapacity, int stock) {
|
this.name = name;
|
this.maxCapacity = maxCapacity;
|
this.unitSpace = 1.0 / maxCapacity;
|
this.stock = stock;
|
this.allocated = 0;
|
}
|
|
public int getRemaining() {
|
return stock - allocated;
|
}
|
|
public boolean allocate(int quantity) {
|
if (allocated + quantity <= stock) {
|
allocated += quantity;
|
return true;
|
}
|
return false;
|
}
|
|
@Override
|
public String toString() {
|
return name + "(单放" + maxCapacity + "个, 库存" + stock + "个)";
|
}
|
}
|
|
static class Locker {
|
int id;
|
double remainingSpace;
|
long bindingTags;
|
Map<String, Integer> contents;
|
Set<String> itemTypes;
|
|
public Locker(int id) {
|
this.id = id;
|
this.remainingSpace = 1.0;
|
this.contents = new HashMap<>();
|
this.itemTypes = new HashSet<>();
|
SnowflakeIdWorker snowflakeIdWorker = SpringUtils.getBean(SnowflakeIdWorker.class);
|
this.bindingTags = snowflakeIdWorker.nextId();
|
}
|
|
public boolean canAdd(Item item, int quantity) {
|
return remainingSpace >= quantity * item.unitSpace;
|
}
|
|
public boolean addItem(Item item, int quantity) {
|
// 验证分配数量
|
if (!item.allocate(quantity)) {
|
return false;
|
}
|
|
double spaceUsed = quantity * item.unitSpace;
|
if (spaceUsed > remainingSpace + 1e-6) {
|
// 回滚分配
|
item.allocated -= quantity;
|
return false;
|
}
|
|
remainingSpace -= spaceUsed;
|
contents.put(item.name, contents.getOrDefault(item.name, 0) + quantity);
|
itemTypes.add(item.name);
|
return true;
|
}
|
|
public boolean containsItemType(String itemName) {
|
return itemTypes.contains(itemName);
|
}
|
|
@Override
|
public String toString() {
|
StringBuilder sb = new StringBuilder();
|
sb.append("储物柜").append(id).append(": ");
|
sb.append(String.format("剩余空间%.4f", remainingSpace)).append("\n");
|
for (Map.Entry<String, Integer> entry : contents.entrySet()) {
|
sb.append(" ").append(entry.getKey()).append(": ").append(entry.getValue()).append("个\n");
|
}
|
return sb.toString();
|
}
|
}
|
|
static class PackingSolution {
|
List<Locker> lockers;
|
int totalLockersUsed;
|
double overallUtilization;
|
int itemTypeChanges;
|
int pureLockers;
|
|
public PackingSolution() {
|
this.lockers = new ArrayList<>();
|
}
|
|
public void addLocker(Locker locker) {
|
lockers.add(locker);
|
totalLockersUsed = lockers.size();
|
}
|
|
public void calculateMetrics() {
|
double totalUsedSpace = 0;
|
itemTypeChanges = 0;
|
pureLockers = 0;
|
String lastItemType = null;
|
|
for (Locker locker : lockers) {
|
totalUsedSpace += (1.0 - locker.remainingSpace);
|
|
if (locker.itemTypes.size() == 1) {
|
pureLockers++;
|
}
|
|
for (String itemType : locker.itemTypes) {
|
if (lastItemType != null && !lastItemType.equals(itemType)) {
|
itemTypeChanges++;
|
}
|
lastItemType = itemType;
|
}
|
}
|
|
overallUtilization = totalUsedSpace / totalLockersUsed;
|
}
|
|
@Override
|
public String toString() {
|
calculateMetrics();
|
StringBuilder sb = new StringBuilder();
|
sb.append("=== 优化摆放方案 ===\n");
|
sb.append("使用的储物柜数量: ").append(totalLockersUsed).append("个\n");
|
sb.append("纯种类储物柜: ").append(pureLockers).append("个\n");
|
sb.append("平均空间利用率: ").append(String.format("%.2f", overallUtilization * 100)).append("%\n");
|
sb.append("物品种类切换次数: ").append(itemTypeChanges).append("次\n\n");
|
|
List<Locker> pureLockersList = new ArrayList<>();
|
List<Locker> mixedLockersList = new ArrayList<>();
|
|
for (Locker locker : lockers) {
|
if (locker.itemTypes.size() == 1) {
|
pureLockersList.add(locker);
|
} else {
|
mixedLockersList.add(locker);
|
}
|
}
|
|
sb.append("【纯种类储物柜】:\n");
|
for (Locker locker : pureLockersList) {
|
sb.append(locker.toString()).append("\n");
|
}
|
|
sb.append("【混合储物柜】:\n");
|
for (Locker locker : mixedLockersList) {
|
sb.append(locker.toString()).append("\n");
|
}
|
|
return sb.toString();
|
}
|
}
|
|
/**
|
* 余料物品辅助类
|
*/
|
private static class RemainderItem {
|
Item item;
|
int quantity;
|
|
RemainderItem(Item item, int quantity) {
|
this.item = item;
|
this.quantity = quantity;
|
}
|
|
@Override
|
public String toString() {
|
return item.name + "(" + quantity + "个)";
|
}
|
|
@Override
|
public boolean equals(Object obj) {
|
if (this == obj) return true;
|
if (obj == null || getClass() != obj.getClass()) return false;
|
RemainderItem that = (RemainderItem) obj;
|
return quantity == that.quantity && item.name.equals(that.item.name);
|
}
|
|
@Override
|
public int hashCode() {
|
return Objects.hash(item.name, quantity);
|
}
|
}
|
|
public static void main(String[] args) {
|
Scanner scanner = new Scanner(System.in);
|
|
System.out.println("请输入物品种类数量:");
|
int itemTypes = scanner.nextInt();
|
scanner.nextLine();
|
|
List<Item> items = new ArrayList<>();
|
|
for (int i = 0; i < itemTypes; i++) {
|
System.out.println("\n请输入第" + (i + 1) + "种物品的信息:");
|
System.out.print("物品名称: ");
|
String name = scanner.nextLine();
|
|
System.out.print("单种存放最大数量: ");
|
int maxCapacity = scanner.nextInt();
|
|
System.out.print("库存数量: ");
|
int stock = scanner.nextInt();
|
scanner.nextLine();
|
|
items.add(new Item(name, maxCapacity, stock));
|
}
|
|
PackingSolution solution = optimizedPacking(items);
|
System.out.println("\n" + solution);
|
|
scanner.close();
|
}
|
|
/**
|
* 优化装箱算法：修复数量管理问题
|
*/
|
public static PackingSolution optimizedPacking(List<Item> items) {
|
// 验证输入
|
if (items == null || items.isEmpty()) {
|
throw new IllegalArgumentException("物品列表不能为空");
|
}
|
|
// 创建物品副本用于处理
|
List<Item> itemsToPack = new ArrayList<>();
|
for (Item item : items) {
|
itemsToPack.add(new Item(item.name, item.maxCapacity, item.stock));
|
}
|
|
PackingSolution solution = new PackingSolution();
|
int lockerId = 1;
|
|
// 第一阶段：对每种物品进行集中处理，分配完整储物柜
|
Map<String, Integer> remainders = new HashMap<>();
|
|
for (Item item : itemsToPack) {
|
if (item.getRemaining() == 0) continue;
|
|
int fullLockersNeeded = item.getRemaining() / item.maxCapacity;
|
int remainder = item.getRemaining() % item.maxCapacity;
|
|
// 分配完整储物柜
|
for (int i = 0; i < fullLockersNeeded; i++) {
|
Locker locker = new Locker(lockerId++);
|
if (locker.addItem(item, item.maxCapacity)) {
|
solution.addLocker(locker);
|
} else {
|
System.out.println("警告: 无法分配完整储物柜给物品 " + item.name);
|
}
|
}
|
|
if (remainder > 0) {
|
remainders.put(item.name, remainder);
|
}
|
}
|
|
// 第二阶段：优化余料分配
|
if (!remainders.isEmpty()) {
|
uniformRemainderProcessing(remainders, itemsToPack, solution, lockerId);
|
}
|
|
// 验证结果
|
if (!validateSolution(items, solution)) {
|
System.out.println("警告: 数量分配验证失败");
|
}
|
|
return solution;
|
}
|
|
/**
|
* 修复后的均匀余料处理算法
|
*/
|
private static void uniformRemainderProcessing(Map<String, Integer> remainders,
|
List<Item> items,
|
PackingSolution solution,
|
int startLockerId) {
|
int lockerId = startLockerId;
|
|
// 将余料转换为可处理的物品列表
|
List<RemainderItem> remainderItems = new ArrayList<>();
|
for (Item item : items) {
|
Integer remainder = remainders.get(item.name);
|
if (remainder != null && remainder > 0 && item.getRemaining() > 0) {
|
remainderItems.add(new RemainderItem(item, Math.min(remainder, item.getRemaining())));
|
}
|
}
|
|
// 按物品单位空间从大到小排序
|
remainderItems.sort((a, b) -> Double.compare(b.item.unitSpace, a.item.unitSpace));
|
|
// 使用修复后的余料处理算法
|
List<Locker> remainderLockers = fixedRemainderArrangement(remainderItems, solution, lockerId);
|
|
// 将最优解添加到解决方案中
|
for (Locker locker : remainderLockers) {
|
solution.addLocker(locker);
|
}
|
}
|
|
/**
|
* 修复后的余料排列方案
|
*/
|
private static List<Locker> fixedRemainderArrangement(List<RemainderItem> remainderItems,
|
PackingSolution solution,
|
int startLockerId) {
|
if (remainderItems.isEmpty()) {
|
return new ArrayList<>();
|
}
|
|
// 创建副本避免修改原始数据
|
List<RemainderItem> remaining = new ArrayList<>();
|
for (RemainderItem ri : remainderItems) {
|
if (ri.quantity > 0) {
|
remaining.add(new RemainderItem(ri.item, ri.quantity));
|
}
|
}
|
|
List<Locker> lockers = new ArrayList<>();
|
int lockerId = startLockerId;
|
|
// 主要策略：创建高利用率储物柜
|
while (!remaining.isEmpty()) {
|
Locker locker = createOptimizedLocker(remaining, lockerId);
|
if (locker != null) {
|
lockers.add(locker);
|
lockerId++;
|
|
// 移除已处理完的物品
|
Iterator<RemainderItem> iterator = remaining.iterator();
|
while (iterator.hasNext()) {
|
RemainderItem ri = iterator.next();
|
if (ri.quantity == 0) {
|
iterator.remove();
|
}
|
}
|
|
double utilization = (1.0 - locker.remainingSpace) * 100;
|
System.out.println("创建储物柜，利用率: " + String.format("%.2f", utilization) + "%");
|
} else {
|
break;
|
}
|
}
|
|
// 处理剩余物品（如果有）
|
if (!remaining.isEmpty()) {
|
System.out.println("使用标准算法处理剩余 " + remaining.size() + " 种物品");
|
List<Locker> standardLockers = standardBestFit(remaining, lockerId);
|
lockers.addAll(standardLockers);
|
}
|
|
return lockers;
|
}
|
|
/**
|
* 创建优化储物柜（修复数量验证）
|
*/
|
private static Locker createOptimizedLocker(List<RemainderItem> remaining, int lockerId) {
|
if (remaining.isEmpty()) {
|
return null;
|
}
|
|
Locker locker = new Locker(lockerId);
|
double targetUtilization = 0.85;
|
double minUtilization = 0.3; // 最低利用率阈值
|
|
// 寻找最佳组合
|
List<RemainderItem> bestCombination = findValidCombination(remaining, targetUtilization);
|
|
if (bestCombination.isEmpty()) {
|
// 尝试达到最低利用率
|
bestCombination = findMinUtilizationCombination(remaining, minUtilization);
|
}
|
|
if (bestCombination.isEmpty()) {
|
return null;
|
}
|
|
// 分配组合到储物柜
|
boolean success = allocateValidCombination(remaining, locker, bestCombination);
|
|
if (!success || locker.contents.isEmpty()) {
|
return null;
|
}
|
|
// 检查利用率是否可接受
|
double utilization = 1.0 - locker.remainingSpace;
|
if (utilization < minUtilization) {
|
// 回滚分配
|
rollbackAllocation(remaining, locker);
|
return null;
|
}
|
|
return locker;
|
}
|
|
/**
|
* 寻找有效组合（修复数量验证）
|
*/
|
private static List<RemainderItem> findValidCombination(List<RemainderItem> items, double targetUtilization) {
|
List<RemainderItem> bestCombination = new ArrayList<>();
|
double[] bestDiff = {Double.MAX_VALUE};
|
|
// 过滤有效物品
|
List<RemainderItem> availableItems = new ArrayList<>();
|
for (RemainderItem ri : items) {
|
if (ri.quantity > 0 && ri.item.getRemaining() > 0) {
|
availableItems.add(ri);
|
}
|
}
|
|
if (availableItems.isEmpty()) {
|
return bestCombination;
|
}
|
|
// 使用DFS搜索有效组合
|
validDfsCombination(availableItems, 0, 0.0, targetUtilization,
|
new ArrayList<>(), bestCombination, bestDiff);
|
|
return bestCombination;
|
}
|
|
/**
|
* 有效的DFS组合搜索
|
*/
|
private static void validDfsCombination(List<RemainderItem> items, int index, double currentSpace,
|
double targetUtilization,
|
List<RemainderItem> current,
|
List<RemainderItem> bestCombination, double[] bestDiff) {
|
// 检查当前组合的有效性
|
if (!current.isEmpty()) {
|
double diff = Math.abs(currentSpace - targetUtilization);
|
if (currentSpace <= 1.0 + 1e-6 && diff < bestDiff[0] && isCombinationValid(current)) {
|
bestCombination.clear();
|
for (RemainderItem ri : current) {
|
bestCombination.add(new RemainderItem(ri.item, ri.quantity));
|
}
|
bestDiff[0] = diff;
|
|
if (diff < 0.01) {
|
return;
|
}
|
}
|
}
|
|
if (index >= items.size() || currentSpace > 1.0 + 1e-6) {
|
return;
|
}
|
|
RemainderItem currentItem = items.get(index);
|
|
// 不选择当前物品
|
validDfsCombination(items, index + 1, currentSpace, targetUtilization,
|
current, bestCombination, bestDiff);
|
|
// 选择当前物品
|
if (currentItem.quantity > 0) {
|
int maxCanAdd = Math.min(currentItem.quantity,
|
(int) Math.floor((1.0 - currentSpace) / currentItem.item.unitSpace));
|
maxCanAdd = Math.min(maxCanAdd, currentItem.item.getRemaining()); // 重要修复：不超过剩余数量
|
|
for (int qty = 1; qty <= maxCanAdd; qty++) {
|
current.add(new RemainderItem(currentItem.item, qty));
|
validDfsCombination(items, index + 1, currentSpace + qty * currentItem.item.unitSpace,
|
targetUtilization, current, bestCombination, bestDiff);
|
current.remove(current.size() - 1);
|
}
|
}
|
}
|
|
/**
|
* 检查组合是否有效（修复数量验证）
|
*/
|
private static boolean isCombinationValid(List<RemainderItem> combination) {
|
Map<String, Integer> totalQuantities = new HashMap<>();
|
|
for (RemainderItem ri : combination) {
|
int currentTotal = totalQuantities.getOrDefault(ri.item.name, 0);
|
totalQuantities.put(ri.item.name, currentTotal + ri.quantity);
|
|
// 检查是否超过物品剩余数量
|
if (currentTotal + ri.quantity > getRemainingQuantity(ri.item)) {
|
return false;
|
}
|
}
|
|
return true;
|
}
|
|
/**
|
* 获取物品剩余数量
|
*/
|
private static int getRemainingQuantity(Item item) {
|
return item.stock - item.allocated;
|
}
|
|
/**
|
* 寻找达到最低利用率的组合
|
*/
|
private static List<RemainderItem> findMinUtilizationCombination(List<RemainderItem> items, double minUtilization) {
|
List<RemainderItem> combination = new ArrayList<>();
|
double currentSpace = 0.0;
|
|
// 按单位空间排序
|
List<RemainderItem> sortedItems = new ArrayList<>(items);
|
sortedItems.sort((a, b) -> Double.compare(b.item.unitSpace, a.item.unitSpace));
|
|
for (RemainderItem ri : sortedItems) {
|
if (ri.quantity > 0 && currentSpace < minUtilization) {
|
int maxCanAdd = Math.min(ri.quantity,
|
(int) Math.floor((1.0 - currentSpace) / ri.item.unitSpace));
|
maxCanAdd = Math.min(maxCanAdd, ri.item.getRemaining()); // 重要修复
|
|
if (maxCanAdd > 0) {
|
combination.add(new RemainderItem(ri.item, maxCanAdd));
|
currentSpace += maxCanAdd * ri.item.unitSpace;
|
}
|
}
|
}
|
|
if (currentSpace >= minUtilization) {
|
return combination;
|
}
|
|
return new ArrayList<>();
|
}
|
|
/**
|
* 分配有效组合到储物柜（修复数量验证）
|
*/
|
private static boolean allocateValidCombination(List<RemainderItem> remaining, Locker locker,
|
List<RemainderItem> combination) {
|
// 验证组合中的所有物品都有足够的数量
|
for (RemainderItem combItem : combination) {
|
boolean found = false;
|
for (RemainderItem remItem : remaining) {
|
if (remItem.item.name.equals(combItem.item.name)) {
|
found = true;
|
if (combItem.quantity > remItem.quantity) {
|
return false;
|
}
|
if (combItem.quantity > remItem.item.getRemaining()) {
|
return false;
|
}
|
break;
|
}
|
}
|
if (!found) {
|
return false;
|
}
|
}
|
|
// 实际分配
|
for (RemainderItem combItem : combination) {
|
for (RemainderItem remItem : remaining) {
|
if (remItem.item.name.equals(combItem.item.name)) {
|
if (locker.addItem(combItem.item, combItem.quantity)) {
|
remItem.quantity -= combItem.quantity;
|
} else {
|
return false;
|
}
|
break;
|
}
|
}
|
}
|
|
return true;
|
}
|
|
/**
|
* 回滚分配
|
*/
|
private static void rollbackAllocation(List<RemainderItem> remaining, Locker locker) {
|
for (Map.Entry<String, Integer> entry : locker.contents.entrySet()) {
|
String itemName = entry.getKey();
|
int quantity = entry.getValue();
|
|
for (RemainderItem ri : remaining) {
|
if (ri.item.name.equals(itemName)) {
|
ri.quantity += quantity;
|
ri.item.allocated -= quantity; // 回滚分配数量
|
break;
|
}
|
}
|
}
|
}
|
|
/**
|
* 标准最佳适应算法
|
*/
|
private static List<Locker> standardBestFit(List<RemainderItem> remainderItems, int startLockerId) {
|
List<Locker> lockers = new ArrayList<>();
|
int lockerId = startLockerId;
|
|
// 创建副本
|
List<RemainderItem> remaining = new ArrayList<>();
|
for (RemainderItem ri : remainderItems) {
|
if (ri.quantity > 0) {
|
remaining.add(new RemainderItem(ri.item, ri.quantity));
|
}
|
}
|
|
// 按单位空间排序
|
remaining.sort((a, b) -> Double.compare(b.item.unitSpace, a.item.unitSpace));
|
|
for (RemainderItem ri : remaining) {
|
while (ri.quantity > 0 && ri.item.getRemaining() > 0) {
|
Locker bestLocker = null;
|
double bestRemainingSpace = Double.MAX_VALUE;
|
|
// 寻找最佳储物柜
|
for (Locker locker : lockers) {
|
if (locker.canAdd(ri.item, 1) && locker.remainingSpace < bestRemainingSpace) {
|
bestLocker = locker;
|
bestRemainingSpace = locker.remainingSpace;
|
}
|
}
|
|
if (bestLocker != null) {
|
int maxCanAdd = (int) Math.floor(bestLocker.remainingSpace / ri.item.unitSpace);
|
int actualAdd = Math.min(ri.quantity, maxCanAdd);
|
actualAdd = Math.min(actualAdd, ri.item.getRemaining()); // 重要修复
|
|
if (actualAdd > 0 && bestLocker.addItem(ri.item, actualAdd)) {
|
ri.quantity -= actualAdd;
|
} else {
|
break;
|
}
|
} else {
|
// 创建新储物柜
|
Locker newLocker = new Locker(lockerId++);
|
int maxCanAdd = (int) Math.floor(1.0 / ri.item.unitSpace);
|
int actualAdd = Math.min(ri.quantity, maxCanAdd);
|
actualAdd = Math.min(actualAdd, ri.item.getRemaining()); // 重要修复
|
|
if (actualAdd > 0 && newLocker.addItem(ri.item, actualAdd)) {
|
lockers.add(newLocker);
|
ri.quantity -= actualAdd;
|
} else {
|
break;
|
}
|
}
|
}
|
}
|
|
return lockers;
|
}
|
|
/**
|
* 验证解决方案（修复验证逻辑）
|
*/
|
private static boolean validateSolution(List<Item> originalItems, PackingSolution solution) {
|
Map<String, Integer> allocatedQuantities = new HashMap<>();
|
Map<String, Integer> originalQuantities = new HashMap<>();
|
|
// 记录原始数量
|
for (Item item : originalItems) {
|
originalQuantities.put(item.name, item.stock);
|
}
|
|
// 计算分配数量
|
for (Locker locker : solution.lockers) {
|
for (Map.Entry<String, Integer> entry : locker.contents.entrySet()) {
|
String itemName = entry.getKey();
|
int quantity = entry.getValue();
|
allocatedQuantities.put(itemName, allocatedQuantities.getOrDefault(itemName, 0) + quantity);
|
}
|
}
|
|
boolean valid = true;
|
for (Map.Entry<String, Integer> entry : originalQuantities.entrySet()) {
|
String itemName = entry.getKey();
|
int originalQty = entry.getValue();
|
int allocatedQty = allocatedQuantities.getOrDefault(itemName, 0);
|
|
if (originalQty != allocatedQty) {
|
System.out.println("验证失败: " + itemName + " 原始数量=" + originalQty +
|
", 分配数量=" + allocatedQty);
|
valid = false;
|
}
|
}
|
|
if (valid) {
|
System.out.println("数量验证通过");
|
}
|
|
return valid;
|
}
|
|
/**
|
* 性能测试和比较
|
*/
|
public static void performanceTest() {
|
System.out.println("=== 性能测试 ===");
|
|
// 测试数据
|
List<Item> testItems = Arrays.asList(
|
new Item("X", 20, 87),
|
new Item("Y", 15, 63),
|
new Item("Z", 34, 125),
|
new Item("T", 25, 48),
|
new Item("U", 40, 92)
|
);
|
|
System.out.println("测试物品数量: " + testItems.size());
|
int totalItems = testItems.stream().mapToInt(item -> item.stock).sum();
|
System.out.println("总物品数量: " + totalItems);
|
|
long startTime = System.currentTimeMillis();
|
PackingSolution solution = optimizedPacking(testItems);
|
long endTime = System.currentTimeMillis();
|
|
System.out.println("\n优化算法结果:");
|
System.out.println("处理时间: " + (endTime - startTime) + "ms");
|
System.out.println("储物柜数量: " + solution.totalLockersUsed);
|
System.out.println("纯种类储物柜: " + solution.pureLockers);
|
System.out.println("空间利用率: " + String.format("%.2f", solution.overallUtilization * 100) + "%");
|
}
|
}
|
