package com.zy.asrs.utils;
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;
        Map<String, Integer> contents;

        public Locker(int id) {
            this.id = id;
            this.remainingSpace = 1.0;
            this.contents = new HashMap<>();
        }

        // 尝试放入物品
        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;
    }
}