如何设计算法来计算多商品优惠后的最大折扣?
时间: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}
答案:
使用回溯法可以解这个问题:
- 求出每个商品的总价和折扣价:根据商品信息和购买数量,计算出每个商品的总价,并应用折扣(单品优惠)。
- 构造满减优惠分组:根据满减优惠信息,将商品分组。同一组内的商品可以使用同一个满减优惠。
- 回溯排列满减分组:使用回溯法,排列满减分组,并选择总价最优的组合。
具体算法实现(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学习网公众号,带你了解更多关于的知识点!
相关阅读
更多>
-
501 收藏
-
501 收藏
-
501 收藏
-
501 收藏
-
501 收藏
最新阅读
更多>
-
128 收藏
-
376 收藏
-
386 收藏
-
178 收藏
-
129 收藏
-
413 收藏
课程推荐
更多>
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 立即学习 542次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 立即学习 507次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 立即学习 497次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 立即学习 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 立即学习 484次学习