如何设计电商满减最优组合算法呢？

[SlipStupig]

在狗东上买东西发现有一个满99 减 10 块的凑单活动，本以为很简单，见过花了很多次计算，才得出一个最优的组合。

然后抽象出问题：满减活动本质是多项式的和，必须尽量大于条件价格 x，且尽量接近 x

然后我又仔细想了一下，如果是暴力排列组合，买了一堆我不太需要的商品，就算满减也没有意义，所有一定存在一个主商品，然后可以搭配其它的一些商品进行组合，所以这个算法该怎么设计能做到最优，让满减得到最优的结构呢？（看起来像是背包问题）

主商品只不过是有一个商品价格是固定的（这个可以交给用户去选哪个是主要商品，价格用户不在乎），剩下就怎么组合尽可能大于等于99，这个值越接近99就越优，至于价格窗口的事情是另外一回事。

我关心的是这个算法这块，并不关心是否真心低于市场价。

问题场景假设

我需要买一包面条价格为：28元

其它参加活动的商品有：

{
"芝麻酱": 16,
"圆珠笔": 2.5,
"醋": 16,
"白醋": 12,
"电池":13,
"酱油套装": 68
}

• 全局最优解为：

  • 与主类商品系同品类，且价格尽量接近99

• 局部最优解为：

  • 与主类商品系非同类商品，价格尽量接近99

[zhangchao12cn]

需要考虑好几个维度，商品重要性，溢价，券的普适性。
最重要的是券的普适性，如果 99-10 可以用来充话费，那么毫无疑问。
其次是商品的溢价和重要性，99-10 理解为 9 折以上，那么必须购买的商品系数×0.9 （大概），次要物品系数 1.0，加权后如果其他渠道价格更低，那么这个商品排除。
在加至 90 至 99 以后，用火腿肠，圆珠笔等低价值消耗品补足。
常见的凑单逻辑就是这样。
鉴于狗东明降暗升的现象非常严重，所以为了节约时间建议非必需商品看都不用看。非必需=可有可无

[tvallday]

我觉得太浪费时间。这个本来是应该立法禁止的。

[turi]

我记得我以前做过一款麻将，
胡牌番型特别多，最终胡牌只能以一种组合胡牌。
不管怎么设计，都会出 bug，
最后暴力穷举所有的胡牌类型组合。
gcc -o2 开启，只能 1000 多人在线，这可能是我做过承载人数最少的游戏了

[Huelse]

很多时候想简单点会比较好。比如满减，你不能让我们的程序去提供，给出一个价格区间的推荐商品，让用户去选就好了

[Takamine]

应该是我这不出来的贪心算法。:doge:

[luozic]

动态规划，改了一个东西全部重算？做好局部最优 其他的让用户自己选，除非最优就是卖点。

[tongzhuoqz]

@tvallday 俺现在就喜欢便利店，厌恶大包小包的购买了，像这种满减俺也参加得越来越少了。

[tongzhuoqz]

@tvallday 也是觉得浪费时间。

[chinesestudio]

没有套路 直接优惠不是更好 浪费用户时间

[reus]

99 减 10 我才懒得理，99-50 的我才会想买多一些，几块钱没必要，几十块才是阈值

[reus]

其实最省钱的，是在低价时买： https://gwdang.com/

很可能满减都还是历史高价的。

[cigarzh]

这还真不是个简单的需求，查了下阿里是用了 Graph Embedding 算法

[SlipStupig]

@reus 满减多少其实一点不重要

@cigarzh 阿里那个场景不一样，我是作为 client 角度去思考这个问题

[loongwang]

@turi 如果空间换时间吗 会不会好点

[vanillaxxx]

之前做这个的时候我也是没有找到很好的思路，后来用了暴力排列组合求最优😂😂😂战略马克

[azh7138m]

我一般是看下张大妈的评论，都是灵性凑单

[reus]

@SlipStupig 如果为了达到所谓“最优”，而买了一些非刚需的东西，其实就是中了它的圈套。不需要的东西，买多少就是亏多少。所以像你的例子，28 的面条，我会买 4 包，满足 99-10 的优惠条件，这样等于每包减了 2.5 元。又或者有其他刚需品，那就先都选中，看够不够 99，不够就调整数量，而不会拿非刚需来凑。
只买刚需，调整数量，我认为这样的策略才是最优的。
满减多少，有时也很重要，例如 28 的面条，有 2000-1000 的券，我也不会用，因为吃到过期都吃不完的……

[turi]

@loongwang 肯定会好点，但是又需要花时间去弄，公司可不会给你这么多时间玩

[SlipStupig]

@reus 需要考虑凑单价格和最优算法啊，至于能不能吃完这个不再考虑范围



@chinesestudio
@reus

两位问题聚焦错了

[zhangchao12cn]

@SlipStupig 价格水分我认为是放在凑单价格和最优算法前第一考虑的。打个比方，电脑 3C 类产品满 1000-100，而你正好有配电脑的需求,其中显示器你觉得很划算是必买。那么，凑单方法 A：显示器 799+SSD 硬盘 239=1038。凑单方法 B：显示器 799+内存条 199+HDMI 线 29=1027。看上去 B 最节约是吧？实际上这条线 pdd 上 9.9 包邮，造成你最后反而多花了 19.1