关于多商品优惠的算法问题，有大佬算法厉害的吗?

Question

大致的思路是这样的，先计算单个商品的多件折扣先，然后得出每个商品的总价格

折扣类型的优惠不需要混合计算，只需要单个商品计算即可，主要是满减优惠，是多商品组合计算的

然后根据每个商品享受的公共满减优惠，组合出最大的优惠，优惠过的商品不能再和其他的商品优惠

有没有大佬用JavaScript或者java实现一遍，救救孩子吧

图片看不清楚可以点击这个看大图
https://image-static.segmentf...

数据库的数据是这样子的

let { multiply } = require("mathjs");

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,
  },
];

// 测试购买的商品，3个A，6个B，3个C
let testBuy = [
  {
    goodsId: 1,
    num: 3,
  },

  {
    goodsId: 2,
    num: 6,
  },

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

testBuy.map((buyItem) => {
  // 先找到购买的这个商品的数据
  let goodsInfo = tb_goods.find((goodsItem) => goodsItem.id == buyItem.goodsId);

  // 得到这个商品的折扣优惠数据
  let spceList = [];
  tb_spce.filter((spceItem) => {
    if (goodsInfo.spceList.includes(spceItem.id)) {
      spceList.push(spceItem);
    }
  });

  // 得出总价
  let money = multiply(goodsInfo.price, buyItem.num);
  // 备用的总价，为了计算折扣使用
  let money2 = multiply(goodsInfo.price, buyItem.num);

  spceList.map((spceItem) => {
    // 是折扣类型的
    if (spceItem.type === "折扣") {
      // 满足大于x件
      if (buyItem.num >= spceItem.full) {
        console.log(spceItem.reduction);
        let reducMoney = multiply(money2, spceItem.reduction);
        if (reducMoney < money) {
          money = reducMoney;
        }
      }
    }

    buyItem.money = money;
  });
});

console.log(testBuy);

// [
//   { goodsId: 1, num: 3, money: 28.5 },
//   { goodsId: 2, num: 6, money: 25.2 },
//   { goodsId: 3, num: 3, money: 16.8 }
// ]

// 最后得出这段数据，然后再次根据多个商品组合出来的满减优惠得出总价格

Answer 1

组合优惠卷问题，基础算法可以使用 回溯法 遍历所有可能性。

下面是参照你的数据格式写的算法，返回结果格式如下：

{
  // 最终折扣后价格
  total: 93.1,
  // 满减总金额
  discount: 11,
  // 使用的满减组合策略
  // 以下表示 商品 1，2 采用 102 满减组合，减了 6 元；
  // 商品 4 可以独立使用 104 满减， 减了 5 元;
  // 一共减了 11 元；
  compose: [
    [
      // 商品ID， 满减金额，自身折扣后金额，满减优惠 ID
      [1, 6, 28.5, 102],
      [2, 6, 25.2, 102],
    ],
    [[4, 5, 33.6, 104]],
  ],
}

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,
  },
];

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));
// {"total":64.5,"discount":6,"compose":[[[1,6,28.5,102],[2,6,25.2,102]]]}

const res3 = compute(demo3);
console.log(JSON.stringify(res3));
// {"total":93.1,"discount":11,"compose":[[[1,6,28.5,102],[2,6,25.2,102]],[[4,5,33.6,104]]]}

const res4 = compute(demo4);
console.log(JSON.stringify(res4));
// {"total":57.1,"discount":5,"compose":[[[1,2,28.5,101]],[[3,3,33.6,103]]]}

const res5 = compute(demo5);
console.log(JSON.stringify(res5));
// {"total":46.9,"discount":4,"compose":[[[1,2,28.5,101]],[[3,2,22.4,101]]]}

const res6 = compute(demo6);
console.log(JSON.stringify(res6));
// {"total":44.599999999999994,"discount":4,"compose":[[[1,2,19,101],[4,2,7,101]],[[2,2,11.4,101],[3,2,11.2,101]]]}

const res7 = compute(demo7);
console.log(JSON.stringify(res7));
// {"total":40.6,"discount":3,"compose":[[[3,3,33.6,103]]]}

Answer 2

策略模式适用你这种场景，可以去了解一下