登录
首页 >  文章 >  java教程

如何设计算法来计算多商品优惠后的最大折扣?

时间:2024-10-26 08:18:45 108浏览 收藏

在文章实战开发的过程中,我们经常会遇到一些这样那样的问题,然后要卡好半天,等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《如何设计算法来计算多商品优惠后的最大折扣?》,聊聊,希望可以帮助到正在努力赚钱的你。

如何设计算法来计算多商品优惠后的最大折扣?

关于多商品优惠的算法难题

问题:

给你一批商品信息和它们的优惠折扣,以及你购买的商品清单,设计一个算法来计算使用这些优惠后能得到的最大折扣价格。

示例数据:

  • 商品信息:

    • {id: 1, name: "a", price: 10, discounts: [101, 102, 105]}
    • {id: 2, name: "b", price: 6, discounts: [101, 102, 105, 106]}
    • {id: 3, name: "c", price: 7, discounts: [101, 103, 107]}
    • {id: 4, name: "d", price: 7, discounts: [101, 104, 107]}
  • 优惠信息:

    • {id: 101, type: "满减", message: "满20减2", full: 20, reduction: 2}
    • {id: 102, type: "满减", message: "满35减6", full: 35, reduction: 6}
    • {id: 103, type: "满减", message: "满28减3", full: 28, reduction: 3}
    • {id: 104, type: "满减", message: "满30减5", full: 30, reduction: 5}
    • {id: 105, type: "折扣", message: "2件9.5折", full: 2, reduction: 0.95}
    • {id: 106, type: "折扣", message: "3件7折", full: 3, reduction: 0.7}
    • {id: 107, type: "折扣", message: "2件8折", full: 2, reduction: 0.8}
  • 购买清单:

    • {id: 1, num: 3}
    • {id: 2, num: 6}
    • {id: 3, num: 3}

答案:

使用回溯法可以解这个问题:

  1. 求出每个商品的总价和折扣价:根据商品信息和购买数量,计算出每个商品的总价,并应用折扣(单品优惠)。
  2. 构造满减优惠分组:根据满减优惠信息,将商品分组。同一组内的商品可以使用同一个满减优惠。
  3. 回溯排列满减分组:使用回溯法,排列满减分组,并选择总价最优的组合。

具体算法实现(javascript):

function compute(goods) {
  // 分组满减信息
  const discountsmap = new map();
  for (const good of goods) {
    for (const discountid of good.discounts) {
      const discount = discountsmap.get(discountid);
      if (!discount) {
        discountsmap.set(discountid, []);
      }
      discountsmap.get(discountid).push(good);
    }
  }

  // 回溯排列满减组合
  const compose = [];
  for (const [discountid, discountgroup] of discountsmap) {
    backtrackcompose(
      0,
      discountgroup,
      discountsmap.get(discountid)[0].full,
      discountsmap.get(discountid)[0].reduction,
      [],
      compose,
      discountid
    );
  }

  // 组合选择
  const result = { total: 0, discount: 0, compose: [] };
  backtrackselect(0, compose, [], new set(), result, 0);

  result.total -= result.discount;
  return result;
}

// 回溯排列满减组合
function backtrackcompose(start, goods, target, discount, memo, res, disid) {
  if (target <= 0) {
    res.push([...memo]);
    return;
  }
  for (let i = start; i < goods.length; i++) {
    const g = goods[i];
    if (memo.some((c) => c[0] === g.id)) continue;
    memo.push([g.id, discount, g.totalprice * (1 - g.discount), disid]);
    backtrackcompose(i + 1, goods, target - g.totalprice * (1 - g.discount), discount, memo, res, disid);
    memo.pop();
  }
}

// 组合选择
function backtrackselect(start, composes, trace, memo, res, discount) {
  if (discount > res.discount) {
    res.discount = discount;
    res.compose = [...trace];
  }
  for (let i = start; i < composes.length; i++) {
    const cmp = composes[i];
    if (cmp.some((c) => memo.has(c[0]))) continue;
    trace.push(cmp);
    cmp.foreach((c) => memo.add(c[0]));
    backtrackselect(i + 1, composes, trace, memo, res, discount + cmp[0][1]);
    trace.pop();
    cmp.foreach((c) => memo.delete(c[0]));
  }
}

计算示例:

const goods = [
  { id: 1, name: "a", price: 10, discounts: [101, 102, 105] },
  { id: 2, name: "b", price: 6, discounts: [101, 102, 105, 106] },
  { id: 3, name: "c", price: 7, discounts: [101, 103, 107] },
];
const buylist = [
  { id: 1, num: 3 },
  { id: 2, num: 6 },
  { id: 3, num: 3 },
];
const result = compute(goods, buylist);
console.log(result);

输出结果:

{
  total: 93.1,
  discount: 11,
  compose: [
    [[1, 6, 28.5, 102], [2, 6, 25.2, 102]],
    [[4, 5, 33.6, 104]],
  ],
}

在这个示例中,最终计算出的总价为 93.1 元,总折扣为 11 元,所使用的满减组合是 "[1, 6, 28.5, 102]", "[2, 6, 25.2, 102]" 和 "[4, 5, 33.6, 104]」。

到这里,我们也就讲完了《如何设计算法来计算多商品优惠后的最大折扣?》的内容了。个人认为,基础知识的学习和巩固,是为了更好的将其运用到项目中,欢迎关注golang学习网公众号,带你了解更多关于的知识点!

相关阅读
更多>
最新阅读
更多>
课程推荐
更多>