package com.zy.asrs.utils;
|
import com.core.common.SnowflakeIdWorker;
|
import com.core.common.SpringUtils;
|
|
import java.util.*;
|
|
public class MultiLockerOptimizerUtils {
|
|
static class Item implements Comparable<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 int compareTo(Item other) {
|
return Double.compare(other.unitSpace, this.unitSpace);
|
}
|
|
@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);
|
item.remaining -= quantity;
|
}
|
|
@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;
|
|
public PackingSolution() {
|
this.lockers = new ArrayList<>();
|
}
|
|
public void addLocker(Locker locker) {
|
lockers.add(locker);
|
totalLockersUsed = lockers.size();
|
}
|
|
public void calculateOverallUtilization() {
|
double totalUsedSpace = 0;
|
for (Locker locker : lockers) {
|
totalUsedSpace += (1.0 - locker.remainingSpace);
|
}
|
overallUtilization = totalUsedSpace / totalLockersUsed;
|
}
|
|
@Override
|
public String toString() {
|
calculateOverallUtilization();
|
StringBuilder sb = new StringBuilder();
|
sb.append("=== 多储物柜摆放方案 ===\n");
|
sb.append("使用的储物柜数量: ").append(totalLockersUsed).append("个\n");
|
sb.append("平均空间利用率: ").append(String.format("%.2f", overallUtilization * 100)).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 = packItems(items);
|
|
System.out.println("\n" + solution);
|
|
scanner.close();
|
}
|
|
/**
|
* 装箱算法：最佳适应递减（Best Fit Decreasing）
|
* 这是装箱问题的经典启发式算法
|
*/
|
public static PackingSolution packItems(List<Item> items) {
|
// 复制物品列表，避免修改原始数据
|
List<Item> itemsToPack = new ArrayList<>();
|
for (Item item : items) {
|
itemsToPack.add(new Item(item.name, item.maxCapacity, item.stock));
|
}
|
|
// 按物品大小从大到小排序（优先处理大物品）
|
Collections.sort(itemsToPack);
|
|
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;
|
}
|
|
/**
|
* 替代算法：首次适应递减（First Fit Decreasing）
|
* 另一种常用的装箱启发式算法
|
*/
|
public static PackingSolution packItemsFirstFit(List<Item> items) {
|
List<Item> itemsToPack = new ArrayList<>();
|
for (Item item : items) {
|
itemsToPack.add(new Item(item.name, item.maxCapacity, item.stock));
|
}
|
|
Collections.sort(itemsToPack);
|
|
PackingSolution solution = new PackingSolution();
|
int lockerId = 1;
|
|
for (Item item : itemsToPack) {
|
while (item.remaining > 0) {
|
boolean placed = false;
|
|
// 尝试放入现有储物柜
|
for (Locker locker : solution.lockers) {
|
if (locker.canAdd(item, 1)) {
|
int maxCanAdd = (int) Math.floor(locker.remainingSpace / item.unitSpace);
|
int actualAdd = Math.min(item.remaining, maxCanAdd);
|
locker.addItem(item, actualAdd);
|
placed = true;
|
break;
|
}
|
}
|
|
// 如果没找到合适的储物柜，创建新的
|
if (!placed) {
|
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 testDifferentAlgorithms() {
|
System.out.println("=== 算法比较测试 ===");
|
|
List<Item> testItems = Arrays.asList(
|
new Item("X", 20, 30),
|
new Item("Y", 15, 25),
|
new Item("Z", 34, 40),
|
new Item("T", 25, 15)
|
);
|
|
System.out.println("测试物品: " + testItems);
|
|
// 测试最佳适应算法
|
PackingSolution bestFitSolution = packItems(testItems);
|
System.out.println("\n最佳适应算法结果:");
|
System.out.println("使用储物柜: " + bestFitSolution.totalLockersUsed + "个");
|
|
// 测试首次适应算法
|
PackingSolution firstFitSolution = packItemsFirstFit(testItems);
|
System.out.println("首次适应算法结果:");
|
System.out.println("使用储物柜: " + firstFitSolution.totalLockersUsed + "个");
|
|
// 显示最佳算法的详细方案
|
System.out.println("\n最佳方案详情:");
|
System.out.println(bestFitSolution);
|
}
|
|
/**
|
* 验证是否所有物品都已摆放
|
*/
|
public static boolean validateSolution(List<Item> originalItems, PackingSolution solution) {
|
Map<String, Integer> totalPlaced = new HashMap<>();
|
|
for (Locker locker : solution.lockers) {
|
for (Map.Entry<String, Integer> entry : locker.contents.entrySet()) {
|
totalPlaced.put(entry.getKey(),
|
totalPlaced.getOrDefault(entry.getKey(), 0) + entry.getValue());
|
}
|
}
|
|
for (Item item : originalItems) {
|
if (totalPlaced.getOrDefault(item.name, 0) != item.stock) {
|
System.out.println("验证失败: " + item.name + " 应放" + item.stock +
|
"个，实放" + totalPlaced.getOrDefault(item.name, 0) + "个");
|
return false;
|
}
|
}
|
|
System.out.println("验证成功: 所有物品都已正确摆放");
|
return true;
|
}
|
}
|
