推荐学习书目 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
这是一个创建于 2320 天前的主题，其中的信息可能已经有所发展或是发生改变。
在狗东上买东西发现有一个满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
 | 1 zhangchao12cn 2019-08-25 03:36:57 +08:00 via iPhone 需要考虑好几个维度，商品重要性，溢价，券的普适性。 最重要的是券的普适性，如果 99-10 可以用来充话费，那么毫无疑问。 其次是商品的溢价和重要性，99-10 理解为 9 折以上，那么必须购买的商品系数×0.9 （大概），次要物品系数 1.0，加权后如果其他渠道价格更低，那么这个商品排除。 在加至 90 至 99 以后，用火腿肠，圆珠笔等低价值消耗品补足。 常见的凑单逻辑就是这样。 鉴于狗东明降暗升的现象非常严重，所以为了节约时间建议非必需商品看都不用看。非必需=可有可无 |
 | 2 tvallday 2019-08-25 08:08:27 +08:00 via Android 我觉得太浪费时间。这个本来是应该立法禁止的。 |
 | 3 turi 2019-08-25 08:30:44 +08:00 我记得我以前做过一款麻将， 胡牌番型特别多，最终胡牌只能以一种组合胡牌。 不管怎么设计，都会出 bug， 最后暴力穷举所有的胡牌类型组合。 gcc -o2 开启，只能 1000 多人在线，这可能是我做过承载人数最少的游戏了 |
 | 4 Huelse 2019-08-25 08:48:57 +08:00 很多时候想简单点会比较好。比如满减，你不能让我们的程序去提供，给出一个价格区间的推荐商品，让用户去选就好了 |
 | 5 Takamine 2019-08-25 09:23:43 +08:00 via Android 应该是我这不出来的贪心算法。:doge: |
 | 6 luozic 2019-08-25 10:47:39 +08:00 via iPhone 动态规划，改了一个东西全部重算？做好局部最优 其他的让用户自己选，除非最优就是卖点。 |
 | 7 tongzhuoqz 2019-08-25 11:00:45 +08:00 @tvallday 俺现在就喜欢便利店，厌恶大包小包的购买了，像这种满减俺也参加得越来越少了。 |
| 8 tongzhuoqz 2019-08-25 11:01:20 +08:00 @tvallday 也是觉得浪费时间。 |
 | 9 chinesestudio 2019-08-25 11:01:47 +08:00 via Android 没有套路 直接优惠不是更好 浪费用户时间 |
 | 10 reus 2019-08-25 11:19:47 +08:00 99 减 10 我才懒得理，99-50 的我才会想买多一些，几块钱没必要，几十块才是阈值 |
| 11 reus 2019-08-25 11:20:35 +08:00 |
 | 12 cigarzh 2019-08-25 12:16:31 +08:00 via iPhone 这还真不是个简单的需求，查了下阿里是用了 Graph Embedding 算法 |
 | 13 SlipStupig OP |
 | 15 vanillaxxx 2019-08-25 14:18:49 +08:00 via iPhone 之前做这个的时候我也是没有找到很好的思路，后来用了暴力排列组合求最优战略马克 |
 | 16 azh7138m 2019-08-25 15:20:22 +08:00 我一般是看下张大妈的评论，都是灵性凑单 |
| 17 reus 2019-08-25 15:51:58 +08:00  1 @SlipStupig 如果为了达到所谓“最优”，而买了一些非刚需的东西，其实就是中了它的圈套。不需要的东西，买多少就是亏多少。所以像你的例子，28 的面条，我会买 4 包，满足 99-10 的优惠条件，这样等于每包减了 2.5 元。又或者有其他刚需品，那就先都选中，看够不够 99，不够就调整数量，而不会拿非刚需来凑。 只买刚需，调整数量，我认为这样的策略才是最优的。 满减多少，有时也很重要，例如 28 的面条，有 2000-1000 的券，我也不会用，因为吃到过期都吃不完的…… |
| 19 SlipStupig OP |
| 20 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 |
Select Language