以相同的方式、算法或数学方程从列表中获取元素

Question

我有一个元素列表ex：[1, 10, 10]，它代表了我拥有的每种类型的产品的数量。用户想要购买各种类型的10产品，一律平等。结果列表将是[1, 5, 4]或[1, 4, 5]。我做了一段时间，循环，迭代列表中的所有元素，如果我没有达到最大数量，增加计数器，直到我得到10个产品，或者所有的库存都是空的。

但是在非常大的数据情况下，我有一些性能问题，我需要在多个位置应用这一点。

我的问题是，如果我能在一个数学方程或更好的算法中做到这一点。对于数学方程，我提取了要求解的数据，但我有太多未知变量：

21/x = a
21/y = b
21/z = c
a + b + c = 10

其中21是所有产品的总和，10是用户需要的产品数量。

Answer 1

O(n)解(带有O(n log(n))分类)：

amounts = [1, 10, 10]
left_to_buy = 12

sorted_amounts = list(sorted([amount, index] for index, amount in enumerate(amounts)))

for idx, (amount, _) in enumerate(sorted_amounts):
    buy = min(left_to_buy//(len(amounts)-idx), amount)
    sorted_amounts[idx][0] -= buy
    left_to_buy -= buy

final_amounts = [a for a, i in sorted(sorted_amounts, key = lambda t: t[1])]
bought = [amount - final_amounts[i] for i, amount in enumerate(amounts)]

print(final_amounts, bought)
#[0, 5, 4] [1, 5, 6]

我们首先对可用项的列表进行排序(我们将它们的索引保存在一个元组中，以便将列表按原来的顺序放在末尾)。

然后，我们从每一件物品中去掉它剩下的部分，如果我们没有足够的东西，我们就把它全部拿走。

最后，我们按原顺序将列表放回原处。

编辑:我错过了你的名单已经被整理好的事实.在这种情况下，它变得更短了：

amounts = [1, 10, 10]
left_to_buy = 12

res = [] 

for idx, amount in enumerate(amounts): 
    buy = min(left_to_buy//(len(amounts)-idx), amount) 
    left_to_buy -= buy 
    res.append(buy) 

print(res) 
# [1, 5, 6]