求个算法，均摊问题

[JinTianYi456]

• 假设现在优惠总额是 1 分钱。价格数组为 [2,3,4] 分钱。
• 要把这 1 分钱均摊到 234 上面。（我这是随便举的例子，1 肯定只能选择 2/3/4 其中一个了
• 要按照 2/3/4 的比例 均摊
• 保证优惠后的价格 [2-?,3-?,4-?] 不为负数
• 以上只是举的例子，应该能理解吧 OvO

[alect]

将优惠分配到价格最低的商品上，直到分配完为止。
1. 先找出最低价格的商品，假设其价格为 p 。
2. 如果优惠的金额大于等于 p ，那么将 p 的价格优惠 1 分钱，并将优惠金额减去 1 分钱。
3. 重复步骤 1 和 2 ，直到优惠金额为 0 或者所有商品的价格都被优惠了。

[JinTianYi456]

@alect #1 忘了一个条件了，要按照 价格数组的比例，均摊，价格越高优惠约多

[JinTianYi456]

不知道这样行不行?
1. 把价格数组按小到大排
2. 循环，按比例均摊（选择一种舍入模式）
3. 如果是最后一条，就把剩下的优惠都分配了

[HuKing]

可以先按照价格数组中的比例计算出每个价格应该分配到的优惠金额，然后再根据每个价格的优惠金额计算出优惠后的价格。具体步骤如下：

1. 首先，将总优惠金额平均分配到价格数组中的每个价格上，得到各个价格应分配到的优惠金额为：

- 价格 2 分钱：1 * 2 / (2 + 3 + 4) = 0.2857 分钱

- 价格 3 分钱：1 * 3 / (2 + 3 + 4) = 0.4286 分钱

- 价格 4 分钱：1 * 4 / (2 + 3 + 4) = 0.2857 分钱

2. 接下来，计算优惠后的价格，即原价格减去分配到的优惠金额。得到的结果应该向下取整到最接近的整数分钱。对于本例，计算出的优惠后的价格为：

- 价格 2 分钱：2 - 0.2857 ≈ 1.7143 分钱，向下取整为 1 分钱

- 价格 3 分钱：3 - 0.4286 ≈ 2.5714 分钱，向下取整为 2 分钱

- 价格 4 分钱：4 - 0.2857 ≈ 3.7143 分钱，向下取整为 3 分钱

[jifengg]

如果允许小数，那么均摊算法很简单。关键就是要取整。
比如优惠 3 分钱，价格数组是[5,5]，那么楼主你期望怎么均摊？也就是你要确定，如何算“均”？

[HuKing]

@HuKing 算的有点问题，思路大致是这个思路

[JinTianYi456]

@HuKing #4 你这不对吧，我这优惠总额才 1 分，你这样算，怎么变成优惠 3 分了?

[JinTianYi456]

@jifengg #5 你看我 3 中的思路行不?

[jifengg]

@JinTianYi456 思路可以，要看你具体的舍入模式，不同模式，有可能导致后面的优惠得多或优惠得少。

建议你先弄几个例子，看看希望怎么分，然后再写算法。

[jmc891205]

1. 循环一遍价格数组求和，并记录下最贵价格的 index
2. 求折扣比例 = 优惠总额 / 价格总额
3. 循环求折扣金额 = 商品价格 * 折扣比例，结果按分向下取整。跳过价格最贵的商品。
4. 最后把剩余的折扣金额分给最贵商品。

O(n)就可以了。不用排序，不然就要 O(nlogn)了

[AllenCai]

function shareDiscount(discount, prices) {
// 计算总价和每个数在总价中所占比例
const total = prices.reduce((acc, cur) => acc + cur);
const ratios = prices.map(price => price / total);

// 分别计算每个数获得的优惠金额并更新它
let remain = discount;
const discounts = ratios.map(ratio => {
const curDiscount = ratio * discount;
remain -= curDiscount;
return curDiscount;
});

// 如果分配完后剩余的优惠金额仍然大于 0 ，则将剩余的优惠金额加到当前值最小的数字上
while (remain > 0) {
// 找到当前最小值和其对应的索引
const minPrice = Math.min(...prices);
const minIndex = prices.indexOf(minPrice);

// 将优惠金额加到最小值上，并保证不会小于 0
const curDiscount = Math.min(remain, discounts[minIndex] + minPrice);
prices[minIndex] -= curDiscount;
discounts[minIndex] += curDiscount;
remain -= curDiscount;
}

// 将每个数字和它对应的优惠金额相加计算最终价格
const finalPrices = prices.map((price, index) => Number((price - discounts[index]).toFixed(2)));
return finalPrices;
}

[alect]

假设顾客买了很多商品，给商品的总价优惠 1%或者其他任意百分比，精度为 1 分钱。
如果要在各个商品上贵的优惠的多，便宜的优惠的少，按比例优惠：

1. 计算出商品价格的总和 sum 。

2. 计算出优惠金额为 discount = sum * 百分比。

3. 将优惠金额转换为分，然后计算每个商品应该优惠的金额 amount = 商品价格 * discount / sum ，然后使用 floor 函数将其向下取整，得到 disAmount 。

4. 计算剩余的优惠金额 total ，即优惠金额 - 所有商品的 disAmount 之和。

5. 对于剩余优惠金额 total ，从商品列表中选择价格向下取整后不等于 0 的商品，并将剩余优惠金额均分到这些商品上，直到剩余优惠金额为 0 。

这个算法会尽量保证每个商品的优惠金额公平地反映在其价格上，并且保证了优惠金额的最小精度为 1 分钱。时间复杂度为 O(n)，其中 n 为商品数量。

示例，
其中 n 表示商品数量，prices 表示商品价格数组，
discountRate 表示折扣率，constant 表示最小精度（ 1 分钱）：

```python
sum = sum(prices)
discount = int(sum * discountRate)
disAmounts = []
total = 0
for i in range(n):
disAmount = int(prices[i] * discount / sum)
total += (prices[i] * discount - disAmount * sum) / constant
disAmounts.append(disAmount)
total = int(round(total)) # 四舍五入，转换为整数
if total > 0:
for i in range(n):
if disAmounts[i] > 0:
disAmounts[i] += total // disAmounts.count(disAmounts[i])
total -= total // disAmounts.count(disAmounts[i])
if total == 0:
break
```

具体怎么搞还得多测一下

[weiwenhao]

先看看这是不是伪需求呀，一般分就是最小单位作为整形吧，小数做数值计算有误差的哦。假如分不是最小单位，那就统一规定 厘 作为最小单位，然后整形存储呗。
假设优惠值是 1 分 = 10 厘）
2,3,4 分钱分配，是不是按比例分配更合理么(按数量分是不是会溢出了)。

(假如按比例分的话，就是 9 份。10 厘分成 9 份，那就 余下一份，这一份怎么分？我们之前好像是随便丢到一个商品上, 如果和需求无关就忽略这个假如)

[weiwenhao]

@alect 我看了一下我们之前倒闭的项目里面，也是这么写的。

```php

/**
* 按照 items totals 等比例分配 amount （ amount 就是折扣总额，单位都是分）
* 返回分配过后的 amount
* @param array $itemsTotals
* @param int $amount
* @return array
*/
private function distributeAmountOfItem(array $itemsTotals, int $amount)
{
$total = array_sum($itemsTotals);
$distributedAmounts = [];

// round(PHP_ROUND_HALF_DOWN) 表示 4 舍 5 入
// 所以最终 array_sum($distributedAmounts) 的值可能大于也可能小于 amount
foreach ($itemsTotals as $item) {
$distributedAmounts[] = (int) round(($item * $amount) / $total, 0, PHP_ROUND_HALF_DOWN);
}

// 余数均分, 如果 missingAmount 是负数，则每一件商品需要把多的折扣 - 回来
$missingAmount = $amount - array_sum($distributedAmounts);
for ($i = 0, $iMax = abs($missingAmount); $i < $iMax; ++$i) {
$distributedAmounts[$i] += $missingAmount >= 0 ? 1 : -1;
}

return $distributedAmounts;
}

```

[shnehna]

第一反应 问 ChatGpt

[fakepoet]

@HuKing 大致是这个思路，但是不能直接向上或向下取整，要用 banker's rounding

[hahasong]

有点像京东合并下单使用优惠券的情况，每个商品都优惠一点。你这都到分了，应该算最小单位不能再分了吧。不如给个具体用例，设计个简化的可行方案

[hahasong]

@JinTianYi456 可以的 也不用留到最后一条。按比例分完，再随机抽一个分剩下的

[gfreezy]

```

def reallocate_prices(total: Decimal, prices: List[Decimal], fraction_number: int = 0) -> List[Decimal]:
"""
把总金额按照 prices 里面各自数目比例均分。
:param total: 总金额
:param prices: 金额的数组
:param fraction_number: 保留小数的位数，最大为 2 位小数
返回均分后的金额数组
假设 total = 10 ，prices = [10, 20, 30, 40]
计算过程是，先把 prices 求和为 sum_prices
主要逻辑就是 new_prices = [
total/sum_prices*10,
total/sum_prices*(10+20) - total/sum_prices*10,
total/sum_prices*(10+20+30) - total/sum_prices*(10+20) - total/sum_prices*10,
total/sum_prices*(10+20+30+40) - total/sum_prices*(10+20+30) - total/sum_prices*(10+20) - total/sum_prices*10
]
"""
total = Decimal(total)
prices = [Decimal(str(p)) for p in prices]
sum_price = sum(prices)
new_prices: List[Decimal] = []
# 用 index 来保留原有的位置
accumulated = Decimal('0')
for price in prices:
accumulated += price
# 按比例分配，并且保留特定的小数位数。
new_price = fraction(total * accumulated / sum_price, fraction_number) - sum(new_prices)
new_prices.append(new_price)

if sum(new_prices) != total:
raise PriceCalculationError
return new_prices

```

[novolei2018]

话说用 swift 怎么写

[unii23i]

马一下

[fano]

可以用 max-min fairness 求解，https://en.wikipedia.org/wiki/Max-min_fairness

[cnoder]

很像部分退款的逻辑