如何使用回溯算法解决多商品优惠问题？

解题思路

对于多商品优惠问题，算法核心是穷举所有可能的优惠组合，并选出其中最优解。本文采用回溯算法实现，步骤如下：

1. 计算单件商品折扣：根据每个商品的优惠折扣信息和数量计算其折扣后总价。
2. 分组分类满减优惠：将满减优惠分组，每组优惠只能应用于同一组商品。
3. 穷举满减组合：使用回溯算法穷举所有可能的满减组合，找出总折扣最大的组合。
4. 确定最佳方案：选择总折扣最大的组合，并计算最终优惠后的总价。

代码示例

上班人导航

上班人必备的职场办公导航网站

下载

以下 javascript 代码提供了具体的解题方案：

let tb_goods = [
  {
    id: 1,
    goodsName: "A",
    price: 10,
    spceList: [101, 102, 105],
  },
  {
    id: 2,
    goodsName: "B",
    price: 6,
    spceList: [101, 102, 105, 106],
  },
  {
    id: 3,
    goodsName: "C",
    price: 7,
    spceList: [101, 103, 107],
  },
  {
    id: 4,
    goodsName: "D",
    price: 7,
    spceList: [101, 104, 107],
  },
];

let tb_spce = [
  {
    id: 101,
    type: "满减",
    msg: "满20减2",
    full: 20,
    reduction: 2,
  },
  {
    id: 102,
    type: "满减",
    msg: "满35减6",
    full: 35,
    reduction: 6,
  },
  {
    id: 103,
    type: "满减",
    msg: "满28减3",
    full: 28,
    reduction: 3,
  },
  {
    id: 104,
    type: "满减",
    msg: "满30减5",
    full: 30,
    reduction: 5,
  },
  {
    id: 105,
    type: "折扣",
    msg: "2件9.5折",
    full: 2,
    reduction: 0.95,
  },
  {
    id: 106,
    type: "折扣",
    msg: "3件7折",
    full: 3,
    reduction: 0.7,
  },
  {
    id: 107,
    type: "折扣",
    msg: "2件8折",
    full: 2,
    reduction: 0.8,
  },
];

let testBuy = [
  {
    goodsId: 1,
    num: 3,
  },

  {
    goodsId: 2,
    num: 6,
  },

  {
    goodsId: 3,
    num: 3,
  },
];

const compute = (goods) => {
  // 初始化变量
  const disGoodsMap = new Map();
  let total = 0;

  // 计算单件商品折扣
  for (let good of goods) {
    const g = tb_goods.find((g) => good.goodsId === g.id);
    good.price = g.price;
    good.totalPrice = g.price * good.num;
    good.totalDisPrice = good.totalPrice;

    // 应用折扣
    g.spceList.forEach((id) => {
      let ts = tb_spce.find((s) => s.id === id);
      if (ts.type === "折扣") {
        if (!ts || good.num < ts.full) return;
        good.totalDisPrice =
          Math.round(
            Math.min(good.totalDisPrice, good.totalPrice * ts.reduction) * 100
          ) / 100;
      } else {
        let gs = disGoodsMap.get(ts);
        if (!gs) {
          gs = [];
          disGoodsMap.set(ts, gs);
        }
        gs.push(good);
      }
    });

    total += good.totalDisPrice;
  }

  // 分组满减优惠
  const compose = [];
  disGoodsMap.forEach((v, k) => {
    disComposeBacktrace(0, v, k.full, k.reduction, [], compose, k.id);
  });

  // 穷举满减组合
  const res = { total: total, discount: 0, compose: [] };
  composeBacktrace(0, compose, [], new Set(), res, 0);
  res.total = res.total - res.discount;

  return res;
};

// 穷举满减组合回溯函数
const composeBacktrace = (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]));
    composeBacktrace(i + 1, composes, trace, memo, res, discount + cmp[0][1]);
    trace.pop();
    cmp.forEach((c) => memo.delete(c[0]));
  }
};

// 分组满减优惠回溯函数
const disComposeBacktrace = (
  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];
    memo.push([g.goodsId, discount, g.totalDisPrice, disId]);
    disComposeBacktrace(i + 1, goods, target - g.totalDisPrice, discount, memo, res, disId);
    memo.pop();
  }
};

const demo1 = [
  { goodsId: 1, num: 3 },
  { goodsId: 3, num: 3 },
];
const demo2 = [
  { goodsId: 1, num: 3 },
  { goodsId: 2, num: 6 },
  { goodsId: 3, num: 3 },
];
const demo3 = [
  { goodsId: 1, num: 3 },
  { goodsId: 2, num: 6 },
  { goodsId: 3, num: 3 },
  { goodsId: 4, num: 6 },
];

const demo4 = [
  { goodsId: 1, num: 3 },
  { goodsId: 3, num: 6 },
];

const demo5 = [
  { goodsId: 1, num: 3 },
  { goodsId: 3, num: 4 },
];

const demo6 = [
  { goodsId: 1, num: 2 },
  { goodsId: 2, num: 2 },
  { goodsId: 3, num: 2 },
  { goodsId: 4, num: 1 },
];

const demo7 = [
  { goodsId: 1, num: 1 },
  { goodsId: 3, num: 6 },
];

const res1 = compute(demo1);
console.log(JSON.stringify(res1));
// {"total":43.3,"discount":2,"compose":[[[1,2,28.5,101]]]}

const res2 = compute(demo2);
console.log(JSON.stringify(res2));