package com.zy.asrs.utils;
|
|
import com.core.common.SnowflakeIdWorker;
|
import com.core.common.SpringUtils;
|
|
import java.util.*;
|
|
public class OptimizedLockerPackingUtils {
|
|
public static class Item {
|
String name;
|
double unitSpace;
|
int maxCapacity;
|
int stock;
|
int remaining;
|
|
public Item(String name, int maxCapacity, int stock) {
|
this.name = name;
|
this.maxCapacity = maxCapacity;
|
this.unitSpace = 1.0 / maxCapacity;
|
this.stock = stock;
|
this.remaining = stock;
|
}
|
|
@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 = System.currentTimeMillis();
|
this.bindingTags = snowflakeIdWorker.nextId();
|
|
}
|
|
public boolean canAdd(Item item, int quantity) {
|
return remainingSpace >= quantity * item.unitSpace;
|
}
|
|
public void addItem(Item item, int quantity) {
|
double spaceUsed = quantity * item.unitSpace;
|
remainingSpace -= spaceUsed;
|
contents.put(item.name, contents.getOrDefault(item.name, 0) + quantity);
|
itemTypes.add(item.name);
|
item.remaining -= quantity;
|
}
|
|
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();
|
}
|
}
|
|
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) {
|
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;
|
|
// 第一阶段：对每种物品进行集中处理
|
for (Item item : itemsToPack) {
|
if (item.remaining == 0) continue;
|
|
// 计算这种物品需要多少个完整的储物柜
|
int fullLockersNeeded = item.remaining / item.maxCapacity;
|
int remainder = item.remaining % item.maxCapacity;
|
|
// 分配完整储物柜
|
for (int i = 0; i < fullLockersNeeded; i++) {
|
Locker locker = new Locker(lockerId++);
|
locker.addItem(item, item.maxCapacity);
|
solution.addLocker(locker);
|
}
|
|
// 如果有余料，暂时保留（第二阶段处理）
|
}
|
|
// 第二阶段：收集所有余料
|
List<Item> remainingItems = new ArrayList<>();
|
for (Item item : itemsToPack) {
|
if (item.remaining > 0) {
|
remainingItems.add(item);
|
}
|
}
|
|
// 如果还有余料，用最佳适应算法处理
|
if (!remainingItems.isEmpty()) {
|
processRemainingItems(remainingItems, solution, lockerId);
|
}
|
|
return solution;
|
}
|
|
/**
|
* 处理剩余物品（余料）
|
*/
|
private static void processRemainingItems(List<Item> remainingItems, PackingSolution solution, int startLockerId) {
|
int lockerId = startLockerId;
|
|
// 按空间占用从大到小排序（优先处理大物品）
|
remainingItems.sort((a, b) -> Double.compare(b.unitSpace, a.unitSpace));
|
|
for (Item item : remainingItems) {
|
while (item.remaining > 0) {
|
// 优先尝试放入已有同种物品的储物柜
|
Locker sameTypeLocker = findSameTypeLocker(solution, item);
|
if (sameTypeLocker != null) {
|
int maxCanAdd = (int) Math.floor(sameTypeLocker.remainingSpace / item.unitSpace);
|
int actualAdd = Math.min(item.remaining, maxCanAdd);
|
sameTypeLocker.addItem(item, actualAdd);
|
continue;
|
}
|
|
// 其次尝试放入现有储物柜（最佳适应）
|
Locker bestLocker = findBestLocker(solution, item);
|
if (bestLocker != null) {
|
int maxCanAdd = (int) Math.floor(bestLocker.remainingSpace / item.unitSpace);
|
int actualAdd = Math.min(item.remaining, maxCanAdd);
|
bestLocker.addItem(item, actualAdd);
|
continue;
|
}
|
|
// 最后创建新储物柜
|
Locker newLocker = new Locker(lockerId++);
|
int maxCanAdd = (int) Math.floor(1.0 / item.unitSpace);
|
int actualAdd = Math.min(item.remaining, maxCanAdd);
|
newLocker.addItem(item, actualAdd);
|
solution.addLocker(newLocker);
|
}
|
}
|
}
|
|
/**
|
* 寻找已有同种物品的储物柜
|
*/
|
private static Locker findSameTypeLocker(PackingSolution solution, Item item) {
|
Locker bestLocker = null;
|
double bestRemaining = -1;
|
|
for (Locker locker : solution.lockers) {
|
if (locker.containsItemType(item.name) && locker.canAdd(item, 1)) {
|
if (locker.remainingSpace > bestRemaining) {
|
bestLocker = locker;
|
bestRemaining = locker.remainingSpace;
|
}
|
}
|
}
|
|
return bestLocker;
|
}
|
|
/**
|
* 寻找最佳适应的储物柜
|
*/
|
private static Locker findBestLocker(PackingSolution solution, Item item) {
|
Locker bestLocker = null;
|
double bestRemaining = Double.MAX_VALUE;
|
|
for (Locker locker : solution.lockers) {
|
if (locker.canAdd(item, 1) && locker.remainingSpace < bestRemaining) {
|
bestLocker = locker;
|
bestRemaining = locker.remainingSpace;
|
}
|
}
|
|
return bestLocker;
|
}
|
|
/**
|
* 高级优化：智能余料分配
|
*/
|
public static PackingSolution advancedOptimizedPacking(List<Item> items) {
|
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.remaining == 0) continue;
|
|
int fullLockers = item.remaining / item.maxCapacity;
|
int remainder = item.remaining % item.maxCapacity;
|
|
for (int i = 0; i < fullLockers; i++) {
|
Locker locker = new Locker(lockerId++);
|
locker.addItem(item, item.maxCapacity);
|
solution.addLocker(locker);
|
}
|
|
if (remainder > 0) {
|
remainders.put(item.name, remainder);
|
}
|
}
|
|
// 第二阶段：智能余料分配
|
if (!remainders.isEmpty()) {
|
smartRemainderProcessing(remainders, itemsToPack, solution, lockerId);
|
}
|
|
return solution;
|
}
|
|
/**
|
* 智能余料处理：尝试将余料组合成完整储物柜
|
*/
|
private static void smartRemainderProcessing(Map<String, Integer> remainders,
|
List<Item> items,
|
PackingSolution solution,
|
int startLockerId) {
|
int lockerId = startLockerId;
|
|
// 尝试找到可以完美组合的余料
|
boolean foundCombination;
|
do {
|
foundCombination = false;
|
|
// 寻找可以填满一个储物柜的余料组合
|
for (Item item1 : items) {
|
if (remainders.getOrDefault(item1.name, 0) == 0) continue;
|
|
for (Item item2 : items) {
|
if (item1.name.equals(item2.name) || remainders.getOrDefault(item2.name, 0) == 0) continue;
|
|
double spaceNeeded = remainders.get(item1.name) * item1.unitSpace +
|
remainders.get(item2.name) * item2.unitSpace;
|
|
if (spaceNeeded <= 1.0 + 1e-6) { // 考虑浮点误差
|
Locker locker = new Locker(lockerId++);
|
locker.addItem(item1, remainders.get(item1.name));
|
locker.addItem(item2, remainders.get(item2.name));
|
solution.addLocker(locker);
|
|
remainders.put(item1.name, 0);
|
remainders.put(item2.name, 0);
|
foundCombination = true;
|
break;
|
}
|
}
|
if (foundCombination) break;
|
}
|
} while (foundCombination);
|
|
// 处理剩余的零散余料
|
for (Item item : items) {
|
int remainder = remainders.getOrDefault(item.name, 0);
|
if (remainder > 0) {
|
Locker bestLocker = findBestLockerForRemainder(solution, item, remainder);
|
if (bestLocker != null) {
|
bestLocker.addItem(item, remainder);
|
} else {
|
Locker newLocker = new Locker(lockerId++);
|
newLocker.addItem(item, remainder);
|
solution.addLocker(newLocker);
|
}
|
}
|
}
|
}
|
|
private static Locker findBestLockerForRemainder(PackingSolution solution, Item item, int quantity) {
|
Locker bestLocker = null;
|
double bestFit = Double.MAX_VALUE;
|
|
for (Locker locker : solution.lockers) {
|
if (locker.canAdd(item, quantity)) {
|
double remainingAfterAdd = locker.remainingSpace - quantity * item.unitSpace;
|
if (remainingAfterAdd < bestFit) {
|
bestLocker = locker;
|
bestFit = remainingAfterAdd;
|
}
|
}
|
}
|
|
return bestLocker;
|
}
|
|
/**
|
* 性能测试和比较
|
*/
|
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) + "%");
|
}
|
}
|
