package com.zy.asrs.utils;
|
|
import java.util.*;
|
|
public class GroupedLockerOptimizerUtils {
|
|
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;
|
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<>();
|
}
|
|
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);
|
}
|
|
// 检查是否可以优先放置同种物品（已有同种物品且还有空间）
|
public boolean canAddSameType(Item item) {
|
return containsItemType(item.name) && canAdd(item, 1);
|
}
|
|
@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; // 物品种类切换次数（衡量集中度）
|
|
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;
|
String lastItemType = null;
|
|
for (Locker locker : lockers) {
|
totalUsedSpace += (1.0 - locker.remainingSpace);
|
|
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(String.format("%.2f", overallUtilization * 100)).append("%\n");
|
sb.append("物品种类切换次数: ").append(itemTypeChanges).append("次（越少越集中）\n\n");
|
|
for (Locker locker : lockers) {
|
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 = packItemsWithGrouping(items);
|
//
|
// System.out.println("\n" + solution);
|
//
|
// scanner.close();
|
// }
|
public static void main(String[] args) {
|
int itemTypes = 5;
|
|
List<Item> items = new ArrayList<>();
|
|
for (int i = 0; i < itemTypes; i++) {
|
String name = i+"a";
|
int maxCapacity = i*10;
|
int stock = i*11;
|
items.add(new Item(name, maxCapacity, stock));
|
}
|
|
// 使用分组优先算法
|
PackingSolution solution = packItemsWithGrouping(items);
|
for (Locker locker:solution.lockers) {
|
for (String mantnr : locker.contents.keySet()){
|
System.out.println(mantnr+"<===>"+locker.contents.get(mantnr));
|
}
|
}
|
System.out.println("\n" + solution);
|
|
// scanner.close();
|
}
|
|
/**
|
* 分组优先装箱算法
|
* 优先将同种物品放在一起，只有在不得已时才分开放置
|
*/
|
public static PackingSolution packItemsWithGrouping(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;
|
|
double totalSpaceNeeded = item.remaining * item.unitSpace;
|
|
// 如果所有物品能放入一个储物柜
|
if (totalSpaceNeeded <= 1.0) {
|
boolean placedInExisting = false;
|
|
// 寻找已有储物柜（优先选择空的）
|
for (Locker locker : solution.lockers) {
|
if (locker.contents.isEmpty() && locker.canAdd(item, item.remaining)) {
|
locker.addItem(item, item.remaining);
|
placedInExisting = true;
|
break;
|
}
|
}
|
|
// 如果没有空储物柜，创建新的
|
if (!placedInExisting) {
|
Locker newLocker = new Locker(lockerId++);
|
newLocker.addItem(item, item.remaining);
|
solution.addLocker(newLocker);
|
}
|
}
|
}
|
|
// 第二阶段：处理剩余物品（无法完整放入一个储物柜的）
|
for (Item item : itemsToPack) {
|
while (item.remaining > 0) {
|
// 优先尝试放入已有同种物品的储物柜
|
Locker bestSameTypeLocker = null;
|
double bestSameTypeSpace = -1;
|
|
for (Locker locker : solution.lockers) {
|
if (locker.containsItemType(item.name) && locker.canAdd(item, 1)) {
|
if (locker.remainingSpace > bestSameTypeSpace) {
|
bestSameTypeLocker = locker;
|
bestSameTypeSpace = locker.remainingSpace;
|
}
|
}
|
}
|
|
if (bestSameTypeLocker != null) {
|
int maxCanAdd = (int) Math.floor(bestSameTypeLocker.remainingSpace / item.unitSpace);
|
int actualAdd = Math.min(item.remaining, maxCanAdd);
|
bestSameTypeLocker.addItem(item, actualAdd);
|
continue;
|
}
|
|
// 其次尝试放入空储物柜（优先集中放置）
|
Locker emptyLocker = null;
|
for (Locker locker : solution.lockers) {
|
if (locker.contents.isEmpty() && locker.canAdd(item, 1)) {
|
emptyLocker = locker;
|
break;
|
}
|
}
|
|
if (emptyLocker != null) {
|
int maxCanAdd = (int) Math.floor(emptyLocker.remainingSpace / item.unitSpace);
|
int actualAdd = Math.min(item.remaining, maxCanAdd);
|
emptyLocker.addItem(item, actualAdd);
|
continue;
|
}
|
|
// 最后尝试放入任何有空间的储物柜
|
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;
|
}
|
}
|
|
if (bestLocker != null) {
|
int maxCanAdd = (int) Math.floor(bestLocker.remainingSpace / item.unitSpace);
|
int actualAdd = Math.min(item.remaining, maxCanAdd);
|
bestLocker.addItem(item, actualAdd);
|
} else {
|
// 创建新储物柜
|
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);
|
}
|
}
|
}
|
|
return solution;
|
}
|
|
/**
|
* 按种类顺序处理算法
|
* 先处理一种物品，再处理下一种
|
*/
|
public static PackingSolution packItemsByType(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) {
|
while (item.remaining > 0) {
|
// 优先使用当前正在处理该类物品的储物柜
|
Locker currentTypeLocker = null;
|
for (Locker locker : solution.lockers) {
|
if (locker.containsItemType(item.name) && locker.canAdd(item, 1)) {
|
currentTypeLocker = locker;
|
break;
|
}
|
}
|
|
if (currentTypeLocker != null) {
|
int maxCanAdd = (int) Math.floor(currentTypeLocker.remainingSpace / item.unitSpace);
|
int actualAdd = Math.min(item.remaining, maxCanAdd);
|
currentTypeLocker.addItem(item, actualAdd);
|
continue;
|
}
|
|
// 如果没有同种物品的储物柜，找空储物柜
|
Locker emptyLocker = null;
|
for (Locker locker : solution.lockers) {
|
if (locker.contents.isEmpty()) {
|
emptyLocker = locker;
|
break;
|
}
|
}
|
|
if (emptyLocker != null) {
|
int maxCanAdd = (int) Math.floor(emptyLocker.remainingSpace / item.unitSpace);
|
int actualAdd = Math.min(item.remaining, maxCanAdd);
|
emptyLocker.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);
|
}
|
}
|
|
return solution;
|
}
|
|
/**
|
* 比较不同算法的效果
|
*/
|
public static void compareAlgorithms() {
|
System.out.println("=== 算法比较 ===");
|
|
List<Item> testItems = Arrays.asList(
|
new Item("X", 20, 35),
|
new Item("Y", 15, 28),
|
new Item("Z", 34, 45),
|
new Item("T", 25, 18)
|
);
|
|
System.out.println("测试物品: " + testItems);
|
|
// 分组优先算法
|
PackingSolution groupedSolution = packItemsWithGrouping(testItems);
|
System.out.println("\n分组优先算法:");
|
System.out.println("储物柜数量: " + groupedSolution.totalLockersUsed);
|
System.out.println("种类切换次数: " + groupedSolution.itemTypeChanges);
|
|
// 按种类顺序算法
|
PackingSolution typeOrderSolution = packItemsByType(testItems);
|
System.out.println("\n按种类顺序算法:");
|
System.out.println("储物柜数量: " + typeOrderSolution.totalLockersUsed);
|
System.out.println("种类切换次数: " + typeOrderSolution.itemTypeChanges);
|
|
// 原始最佳适应算法（不分组）
|
PackingSolution originalSolution = packItemsOriginal(testItems);
|
System.out.println("\n原始最佳适应算法:");
|
System.out.println("储物柜数量: " + originalSolution.totalLockersUsed);
|
System.out.println("种类切换次数: " + originalSolution.itemTypeChanges);
|
}
|
|
/**
|
* 原始最佳适应算法（不分组，作为对比）
|
*/
|
public static PackingSolution packItemsOriginal(List<Item> items) {
|
List<Item> itemsToPack = new ArrayList<>();
|
for (Item item : items) {
|
itemsToPack.add(new Item(item.name, item.maxCapacity, item.stock));
|
}
|
|
// 按空间占用从大到小排序
|
itemsToPack.sort((a, b) -> Double.compare(b.unitSpace, a.unitSpace));
|
|
PackingSolution solution = new PackingSolution();
|
int lockerId = 1;
|
|
for (Item item : itemsToPack) {
|
while (item.remaining > 0) {
|
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;
|
}
|
}
|
|
if (bestLocker != null) {
|
int maxCanAdd = (int) Math.floor(bestLocker.remainingSpace / item.unitSpace);
|
int actualAdd = Math.min(item.remaining, maxCanAdd);
|
bestLocker.addItem(item, actualAdd);
|
} else {
|
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);
|
}
|
}
|
}
|
|
return solution;
|
}
|
|
/**
|
* 可视化展示储物柜使用情况
|
*/
|
// public static void visualizeSolution(PackingSolution solution) {
|
// System.out.println("=== 储物柜使用情况可视化 ===");
|
//
|
// for (Locker locker : solution.lockers) {
|
// System.out.println("储物柜 " + locker.id + ":");
|
// for (Map.Entry<String, Integer> entry : locker.contents.entrySet()) {
|
// int barLength = (int) (entry.getValue() * 50 / (1.0 / 0.05)); // 简化可视化
|
// String bar = "=".repeat(barLength);
|
// System.out.printf(" %s: %s %d个\n", entry.getKey(), bar, entry.getValue());
|
// }
|
// System.out.printf(" 剩余空间: %.2f%%\n", locker.remainingSpace * 100);
|
// System.out.println();
|
// }
|
// }
|
|
public static void visualizeSolution(PackingSolution solution) {
|
System.out.println("=== 储物柜使用情况可视化 ===");
|
|
for (Locker locker : solution.lockers) {
|
System.out.println("储物柜 " + locker.id + ":");
|
for (Map.Entry<String, Integer> entry : locker.contents.entrySet()) {
|
int barLength = (int) (entry.getValue() * 50 / (1.0 / 0.05));
|
|
// 替代 String.repeat()
|
StringBuilder barBuilder = new StringBuilder();
|
for (int i = 0; i < barLength; i++) {
|
barBuilder.append("=");
|
}
|
String bar = barBuilder.toString();
|
|
System.out.printf(" %s: %s %d个\n", entry.getKey(), bar, entry.getValue());
|
}
|
System.out.printf(" 剩余空间: %.2f%%\n", locker.remainingSpace * 100);
|
System.out.println();
|
}
|
}
|
}
|
