V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
JinTianYi456
V2EX  ›  问与答

求个算法,均摊问题

  •  
  •   JinTianYi456 · 351 天前 · 2240 次点击
    这是一个创建于 351 天前的主题,其中的信息可能已经有所发展或是发生改变。
    • 假设现在优惠总额是 1 分钱。价格数组为 [2,3,4] 分钱。
    • 要把这 1 分钱均摊到 234 上面。(我这是随便举的例子,1 肯定只能选择 2/3/4 其中一个了
    • 要按照 2/3/4 的比例 均摊
    • 保证优惠后的价格 [2-?,3-?,4-?] 不为负数
    • 以上只是举的例子,应该能理解吧 OvO
    23 条回复    2023-04-13 18:30:08 +08:00
    alect
        1
    alect  
       351 天前
    将优惠分配到价格最低的商品上,直到分配完为止。
    1. 先找出最低价格的商品,假设其价格为 p 。
    2. 如果优惠的金额大于等于 p ,那么将 p 的价格优惠 1 分钱,并将优惠金额减去 1 分钱。
    3. 重复步骤 1 和 2 ,直到优惠金额为 0 或者所有商品的价格都被优惠了。
    JinTianYi456
        2
    JinTianYi456  
    OP
       351 天前
    @alect #1 忘了一个条件了,要按照 价格数组的比例,均摊,价格越高优惠约多
    JinTianYi456
        3
    JinTianYi456  
    OP
       351 天前
    不知道这样行不行?
    1. 把价格数组按小到大排
    2. 循环,按比例均摊(选择一种舍入模式)
    3. 如果是最后一条,就把剩下的优惠都分配了
    HuKing
        4
    HuKing  
       351 天前
    可以先按照价格数组中的比例计算出每个价格应该分配到的优惠金额,然后再根据每个价格的优惠金额计算出优惠后的价格。具体步骤如下:

    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
        5
    jifengg  
       351 天前
    如果允许小数,那么均摊算法很简单。关键就是要取整。
    比如优惠 3 分钱,价格数组是[5,5],那么楼主你期望怎么均摊?也就是你要确定,如何算“均”?
    HuKing
        6
    HuKing  
       351 天前
    @HuKing 算的有点问题,思路大致是这个思路
    JinTianYi456
        7
    JinTianYi456  
    OP
       351 天前
    @HuKing #4 你这不对吧,我这优惠总额才 1 分,你这样算,怎么变成优惠 3 分了?
    JinTianYi456
        8
    JinTianYi456  
    OP
       351 天前
    @jifengg #5 你看我 3 中的思路行不?
    jifengg
        9
    jifengg  
       351 天前
    @JinTianYi456 思路可以,要看你具体的舍入模式,不同模式,有可能导致后面的优惠得多或优惠得少。

    建议你先弄几个例子,看看希望怎么分,然后再写算法。
    jmc891205
        10
    jmc891205  
       351 天前   ❤️ 3
    1. 循环一遍价格数组求和,并记录下最贵价格的 index
    2. 求折扣比例 = 优惠总额 / 价格总额
    3. 循环求折扣金额 = 商品价格 * 折扣比例,结果按分向下取整。跳过价格最贵的商品。
    4. 最后把剩余的折扣金额分给最贵商品。

    O(n)就可以了。不用排序,不然就要 O(nlogn)了
    AllenCai
        11
    AllenCai  
       351 天前
    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
        12
    alect  
       351 天前
    假设顾客买了很多商品,给商品的总价优惠 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
        13
    weiwenhao  
       351 天前
    先看看这是不是伪需求呀,一般分就是最小单位作为整形吧,小数做数值计算有误差的哦。假如分不是最小单位,那就统一规定 厘 作为最小单位,然后整形存储呗。
    假设优惠值是 1 分 = 10 厘)
    2,3,4 分钱分配,是不是按比例分配更合理么(按数量分是不是会溢出了)。

    (假如按比例分的话,就是 9 份。10 厘分成 9 份,那就 余下一份,这一份怎么分?我们之前好像是随便丢到一个商品上, 如果和需求无关就忽略这个假如)
    weiwenhao
        14
    weiwenhao  
       351 天前
    @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
        15
    shnehna  
       351 天前
    第一反应 问 ChatGpt
    fakepoet
        16
    fakepoet  
       351 天前
    @HuKing 大致是这个思路,但是不能直接向上或向下取整,要用 banker's rounding
    hahasong
        17
    hahasong  
       351 天前
    有点像京东合并下单使用优惠券的情况,每个商品都优惠一点。你这都到分了,应该算最小单位不能再分了吧。不如给个具体用例,设计个简化的可行方案
    hahasong
        18
    hahasong  
       351 天前
    @JinTianYi456 可以的 也不用留到最后一条。按比例分完,再随机抽一个分剩下的
    gfreezy
        19
    gfreezy  
       351 天前
    ```

    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
        20
    novolei2018  
       351 天前
    话说用 swift 怎么写
    unii23i
        21
    unii23i  
       351 天前
    马一下
    fano
        22
    fano  
       351 天前
    可以用 max-min fairness 求解,https://en.wikipedia.org/wiki/Max-min_fairness
    cnoder
        23
    cnoder  
       351 天前
    很像部分退款的逻辑
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2780 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 12:52 · PVG 20:52 · LAX 05:52 · JFK 08:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.