点外卖的时候不是有满减吗,如何用算法实现最优的点餐组合?即最终合计与满减的值最接近。 比如满 35 减 24,每份菜的价格是已知的,如何算出怎么点菜可以与 35 最接近,当然要比 35 大了。
1
wingkou 2018-08-07 11:17:09 +08:00 via Android
这不就是线性规划吗?
|
2
timboy 2018-08-07 11:37:43 +08:00
背包问题?
|
3
murmur 2018-08-07 11:40:05 +08:00
需求在哪里呢?
点餐不是按喜欢吃和吃多少点么 满 35 减 24 等你点了结账就发现会多出几块钱的饭盒费和派送费 |
4
dingyaguang117 2018-08-07 11:42:04 +08:00
背包问题
|
5
enenaaa 2018-08-07 11:42:15 +08:00
从全排列开始。逐个条件裁剪掉不必要的路径。再以动态规划策略利用到历史步骤的结果。
|
7
rabbbit 2018-08-07 11:59:15 +08:00
允许重复点同一个菜吗?
|
8
geelaw 2018-08-07 12:00:55 +08:00
这个问题是 NP-H,很明显它可以用来解子集和。
买化妆品的版本(单纯的子集和归约) https://geelaw.blog/entries/galeries-lafayette-discount-npc/ 买内裤的版本(有更加复杂的优惠规则) https://www.weibo.com/2389742313/GjmvmAQd6 |
9
jasonMakarov 2018-08-07 12:01:34 +08:00
KNN 考虑下吧
|
10
streamo 2018-08-07 12:02:29 +08:00
因为你要求具体方案所以不是背包。比较容易想到的办法是用 DFS 求排列组合然后在结果集里挑。
|
12
rabbbit 2018-08-07 12:07:57 +08:00
这个比较像 leetcode 40 题
给出一个数组和目标值,求数组元素和等于目标值的可能组合 https://leetcode.com/problems/combination-sum-ii/description/ 想了好久也不出怎么用动态规划做... |
14
wkan 2018-08-07 12:10:41 +08:00 via Android
点最便宜的那个,多点几份是最接近的
|
16
lychnis 2018-08-07 12:20:30 +08:00 via Android
点外卖 你这样算出来的你愿意吃吗。。。
|
18
murmur 2018-08-07 12:23:48 +08:00
|
19
murmur 2018-08-07 12:24:01 +08:00
*更正:没有需求怎么谈算法
|
21
shakespaces 2018-08-07 12:27:24 +08:00 via Android
对于外卖这种,一个店里最多也就几十种菜品,直接一个暴力就结束了😂
|
23
rabbbit 2018-08-07 12:29:41 +08:00
搞错了,应该是和 39 题比较像,因为可以重复点菜.
暴力搜索... ``` var combinationSum = function (candidates, target) { let min = Infinity; let solution = []; len = candidates.length; let callback = function (i, target, arr) { if (target <= 0 && Math.abs(target) <= min) { if (Math.abs(target) === min) { solution.push(arr.slice()); } else { solution = [arr.slice()]; } min = Math.abs(target); } else if (target > 0) { while (i < len) { arr.push(candidates[i]); callback(i, target - candidates[i], arr); arr.pop(); i++; } } } callback(0, target, []); return [min, solution]; }; console.log(combinationSum([1], 2)); // [ 0, [ [ 1, 1 ] ] ] console.log(combinationSum([1, 2], 3.1)); // [ 0.8999999999999999, [ [ 1, 1, 1, 1 ], [ 1, 1, 2 ], [ 2, 2 ] ] ] console.log(combinationSum([1, 2, 3], 5)); // [ 0, [ [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 2 ], [ 1, 1, 3 ], [ 1, 2, 2 ], [ 2, 3 ] ] ] ``` |
24
rabbbit 2018-08-07 12:32:16 +08:00
|
26
ppyybb 2018-08-07 12:44:40 +08:00 via iPhone 1
如果要求用户至少花费 k 元,那么可以提供一个思路:
假设不妨设一共 N 个菜,设状态 dp[i][S] 为处理了前 i 个菜,一共点了 S 的价格的状态(0 表示不存在这个状态,1 表示存在这个状态) 先不考虑满减,显然 dp[i + 1][S + price[i + 1]] dp[i+1][S] = dp[S] 所以 dp[N-1]表示所有菜都考虑了的情况,那么考虑满减 dp[N-1][S] - discount (如果有多个满减,就找最近点那一个) 结果就是最小的那个 这种情况如果 S 的总价格不是很大,那么状态不会很多(我们可以假设用户不会点超过 1000 的外卖,S <= 1000,如果超过一般都会超过最大的满减上限了) 也就是搜索一个 N * S 的状态空间就可以解决 优化空间: 显然 dp[i]只依赖 dp[i-1],所以两个一维数组就可以解决 剪枝: 保留当前最小的 S - discount,那么我们可以判断从当前状态出发是否存在更小的可能,这里分类讨论可能的 discount 缓存: 从业务考虑,我们完全可以先计算好前 100 个状态,然后需要的时候直接从缓存好的状态开始计算起(时间和空间的 tradeoff) |
27
Biwood 2018-08-07 12:51:52 +08:00
我想说,抛开技术不谈,这类满减活动多半只是为了让你多消费而已。
判断是否真的优惠只有一个办法,首先别看优惠活动,先选好所有你想要的东西,然后再看优惠活动规则。如果参与优惠比当前订单金额小,那么就是值得的。如果参与优惠后,金额比之前增多,说明你只是用“看起来更便宜”的价格买了你不需要的东西而已。 |
28
MiffyLiye 2018-08-07 13:14:42 +08:00
暴力解法有穷举。
半暴力解法有 backtracking 和 branch and bound。 随便加点额外的约束,例如需要包含特定种类、限定特定种类的数量,搜索过程就能快很多。 |
29
ryuzaki113 2018-08-07 14:04:42 +08:00
说个题外话,外卖满减再多不如去店里吃
|
30
zhzer 2018-08-07 14:32:12 +08:00
动态规划
|
31
PulpFunction 2018-08-07 17:08:56 +08:00
1。先拿到所有的优惠满减信息
2。你得有一个预计花钱的参数吧 3。把 1 里面的价格相减,算出每一个优惠信息的低消 4。排序 选择一个比预计花钱少的 选一个比预计花钱多的;或者多选点 反正就是几个下标的问题 |
32
PulpFunction 2018-08-07 17:12:19 +08:00
5。凑钱 选主食和配菜( 0.获取主食套餐与小吃) 超出预期越少的越实惠,有时候多一点更实惠。。
|
33
stephenyin 2018-08-07 17:54:27 +08:00
@ryuzaki113 #29 绝大多数外卖满减+平台补贴后都比店里便宜.
|
34
tt67wq 2018-08-08 07:38:53 +08:00 via Android
有个比较经典的背包问题,跟这个差不多吧
|