Minecraft最大化合成次数的物品购买次数计算算法修正求助

问题分析 #

原算法的核心错误在于对背包空间、物品加工规则的理解偏差：

1. 错误将背包总空间统一按每格64计算，忽略不同物品的堆叠上限差异；
2. 未考虑烈焰棒加工成烈焰粉后数量翻倍的规则，导致物品2的购买次数计算错误；
3. 合成次数的计算逻辑完全偏离实际的格子占用与物品需求关系，导致结果偏大。

修正思路 #

我们需要找到最大合成次数k，同时计算满足以下条件的最小购买次数x（物品1）和y（物品2）：

• 物品1总数量：64x ≥ k*item1（单次合成需item1个，每次购买得64个）
• 物品2总成品数量：128y ≥ k*item2（单次购买64个烈焰棒，加工后得128个烈焰粉）
• 背包格子占用：存放物品1的格子数 + 存放物品2的格子数 ≤ 36（物品2的格子数按原材料烈焰棒的堆叠数计算）

其中，格子数计算采用向上取整（物品不满一格也需占用一格），公式为(总物品数 + 堆叠上限 - 1) // 堆叠上限。

修正后的Java代码 #

public static int[] calcAmount(int item1, int stacksize1, int item2, int stacksize2, int invSlots) {
    int maxK = 0;
    int bestX = 0;
    int bestY = 0;

    // 计算理论最大可能的合成次数上限，避免无效遍历
    int maxPossibleK1 = (invSlots * stacksize1) / item1;
    int maxPossibleK2 = (invSlots * stacksize2 * 2) / item2;
    int upperLimit = Math.max(maxPossibleK1, maxPossibleK2) + 1;

    for (int k = 0; k <= upperLimit; k++) {
        // 计算满足k次合成所需的最小购买次数（向上取整）
        int requiredX = (k * item1 + 63) / 64;
        int requiredY = (k * item2 + 127) / 128;

        // 计算两种物品占用的背包格子数
        int slots1 = (64 * requiredX + stacksize1 - 1) / stacksize1;
        int slots2 = (64 * requiredY + stacksize2 - 1) / stacksize2;

        // 更新最大合成次数及对应购买次数
        if (slots1 + slots2 <= invSlots && k > maxK) {
            maxK = k;
            bestX = requiredX;
            bestY = requiredY;
        }
    }

    return new int[]{bestX, bestY};
}

测试示例 #

输入：calcAmount(32, 16, 128, 32, 36)
输出：[4, 8]，与预期一致。

内容的提问来源于stack exchange，提问作者Jonas