关于多商品优惠的算法难题
问题：
给你一批商品信息和它们的优惠折扣，以及你购买的商品清单，设计一个算法来计算使用这些优惠后能得到的最大折扣价格。
示例数据：
商品信息：
{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}
购买清单：
算家云
高效、便捷的人工智能算力服务平台
37 查看详情 {id: 1, num: 3}{id: 2, num: 6}{id: 3, num: 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 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 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]」。
以上就是如何设计算法来计算多商品优惠后的最大折扣？的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/450662.html
微信扫一扫 
支付宝扫一扫 
