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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 1927 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

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

第 1 条附言 · 2019-08-25 09:18:27 +08:00

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

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

问题场景假设

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

其它参加活动的商品有：

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

全局最优解为：
- 与主类商品系同品类，且价格尽量接近99
局部最优解为：
- 与主类商品系非同类商品，价格尽量接近99

组合

算法

狗东

商品

20 条回复 • 2019-08-26 00:12:03 +08:00

zhangchao12cn

2019-08-25 03:36:57 +08:00 via iPhone

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

tvallday

2019-08-25 08:08:27 +08:00 via Android

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

turi

2019-08-25 08:30:44 +08:00

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

Huelse

2019-08-25 08:48:57 +08:00

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

Takamine

2019-08-25 09:23:43 +08:00 via Android

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

luozic

2019-08-25 10:47:39 +08:00 via iPhone

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

tongzhuoqz

2019-08-25 11:00:45 +08:00

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

tongzhuoqz

2019-08-25 11:01:20 +08:00

@tvallday 也是觉得浪费时间。

chinesestudio

2019-08-25 11:01:47 +08:00 via Android

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

reus

2019-08-25 11:19:47 +08:00

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

reus

2019-08-25 11:20:35 +08:00

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

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

cigarzh

2019-08-25 12:16:31 +08:00 via iPhone

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

SlipStupig

2019-08-25 12:43:57 +08:00

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

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

loongwang

2019-08-25 13:16:59 +08:00

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

vanillaxxx

2019-08-25 14:18:49 +08:00 via iPhone

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

azh7138m

2019-08-25 15:20:22 +08:00

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

reus

2019-08-25 15:51:58 +08:00

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

turi

2019-08-25 16:25:19 +08:00

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

SlipStupig

2019-08-25 22:19:45 +08:00

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

@chinesestudio
@reus

两位问题聚焦错了

zhangchao12cn

2019-08-26 00:12:03 +08:00

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