最大合金数

难度: Medium

假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。

对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有 stock[i] 份 i 类型金属，而每购入一份 i 类型金属需要花费 cost[i] 的金钱。

给你整数 n、k、budget，下标从 1 开始的二维数组 composition，两个下标从 1 开始的数组 stock 和 cost，请你在预算不超过 budget 金钱的前提下，最大化 公司制造合金的数量。

所有合金都需要由同一台机器制造。

返回公司可以制造的最大合金数。

示例 1：

输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3]
输出：2
解释：最优的方法是使用第 1 台机器来制造合金。
要想制造 2 份合金，我们需要购买：
- 2 份第 1 类金属。
- 2 份第 2 类金属。
- 2 份第 3 类金属。
总共需要 2 * 1 + 2 * 2 + 2 * 3 = 12 的金钱，小于等于预算 15 。
注意，我们最开始时候没有任何一类金属，所以必须买齐所有需要的金属。
可以证明在示例条件下最多可以制造 2 份合金。

示例 2：

输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,100], cost = [1,2,3]
输出：5
解释：最优的方法是使用第 2 台机器来制造合金。 
要想制造 5 份合金，我们需要购买： 
- 5 份第 1 类金属。
- 5 份第 2 类金属。 
- 0 份第 3 类金属。 
总共需要 5 * 1 + 5 * 2 + 0 * 3 = 15 的金钱，小于等于预算 15 。 
可以证明在示例条件下最多可以制造 5 份合金。

示例 3：

输入：n = 2, k = 3, budget = 10, composition = [[2,1],[1,2],[1,1]], stock = [1,1], cost = [5,5]
输出：2
解释：最优的方法是使用第 3 台机器来制造合金。
要想制造 2 份合金，我们需要购买：
- 1 份第 1 类金属。
- 1 份第 2 类金属。
总共需要 1 * 5 + 1 * 5 = 10 的金钱，小于等于预算 10 。
可以证明在示例条件下最多可以制造 2 份合金。

提示：

1 <= n, k <= 100
0 <= budget <= 10⁸
composition.length == k
composition[i].length == n
1 <= composition[i][j] <= 100
stock.length == cost.length == n
0 <= stock[i] <= 10⁸
1 <= cost[i] <= 100

Submission

运行时间: 66 ms

内存: 16.5 MB

class Solution:
    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
        def f(com):
            alloy_cost, stock_cost = 0, 0
            for num, p, s, c in sorted([[s//p, p, s, c] for p, s, c in zip(com, stock, cost)]):
                if alloy_cost * num - stock_cost > budget: break
                alloy_cost += p*c
                stock_cost += s*c
            return (stock_cost + budget) // alloy_cost
        return max(map(f, composition))

Explain

这个题解使用了一个贪心的方法来为每台机器计算最大可能制造的合金数量。对于每一台机器，它计算了在当前预算下每种金属可以制造的合金数量的上限，并按照这个上限升序排序。这样，每次需要额外购买最少的金属数量来制造更多的合金。分析完毕后，它计算了在当前预算下可以制造的最大合金数量。最后，通过对所有机器重复这一过程，找到并返回可以制造最多合金的机器的结果。

时间复杂度: O(k * n log n)

空间复杂度: O(n)

class Solution:
    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
        def f(com):
            # 初始化合金成本和库存成本
            alloy_cost, stock_cost = 0, 0
            # 排序金属按照 '可以制造的合金数' 的升序
            for num, p, s, c in sorted([[s//p, p, s, c] for p, s, c in zip(com, stock, cost)]):
                # 如果增加当前金属超出预算，中断循环
                if alloy_cost * num - stock_cost > budget: break
                # 更新合金成本和库存成本
                alloy_cost += p*c
                stock_cost += s*c
            # 计算在预算内可以制造的最大合金数
            return (stock_cost + budget) // alloy_cost
        # 对每一台机器应用函数f，并找出可以制造最多合金的机器
        return max(map(f, composition))

Explore

贪心算法在这个问题中被选用是因为它提供了一种直观而高效的方法来逐步优化决策，即优先购买单位成本下能增加更多合金数量的金属。这种方法通常比动态规划更简单且执行效率更高，特别是在问题规模较大时。动态规划虽然可以处理更复杂的依赖情况，但在此问题中可能导致不必要的计算复杂性和更高的时间及空间成本。

排序的依据是每种金属使用当前库存能制造的合金数量，即库存量除以每单位合金所需的该金属量。按照'可以制造的合金数'的升序进行排序的目的是优先处理那些制造合金数量较少的金属。这样做是因为处理这些金属可能需要较少的预算增量，从而在预算有限的情况下，尽可能多地制造合金。

这种做法基于贪心算法的局限性，可能会导致未找到实际的最大合金数。因为这种方法是依据当前排序和预算决定是否继续购买，而不是全面考虑所有可能的购买组合。这可能导致某些情况下，通过不同的购买策略（可能初期成本较高但长远更经济）能够制造更多的合金。

`stock_cost`是指使用现有库存的金属的总成本，计算方式是每种金属的库存量乘以该金属的单价的总和。`alloy_cost`是指在购买额外金属后，每生产一个单位合金的平均成本，这是通过将每种金属的单价与每单位合金所需的金属量相乘并累加得到的。公式中的`(stock_cost + budget) // alloy_cost`表示在有限预算内最多可以制造的合金数量。