问一个算法的思路

点外卖的时候不是有满减吗，如何用算法实现最优的点餐组合？即最终合计与满减的值最接近。比如满 35 减 24，每份菜的价格是已知的，如何算出怎么点菜可以与 35 最接近，当然要比 35 大了。

murmur

2018 年 8 月 7 日

需求在哪里呢？
点餐不是按喜欢吃和吃多少点么
满 35 减 24 等你点了结账就发现会多出几块钱的饭盒费和派送费

enenaaa

2018 年 8 月 7 日

从全排列开始。逐个条件裁剪掉不必要的路径。再以动态规划策略利用到历史步骤的结果。

waiaan

2018 年 8 月 7 日

@murmur 不是，只是偶然想到这个问题，跟具体点餐的事情没关系。

geelaw

2018 年 8 月 7 日

这个问题是 NP-H，很明显它可以用来解子集和。

买化妆品的版本（单纯的子集和归约）

https://geelaw.blog/entries/galeries-lafayette-discount-npc/

买内裤的版本（有更加复杂的优惠规则）

https://www.weibo.com/2389742313/GjmvmAQd6

streamo

2018 年 8 月 7 日

因为你要求具体方案所以不是背包。比较容易想到的办法是用 DFS 求排列组合然后在结果集里挑。

rabbbit

2018 年 8 月 7 日

这个比较像 leetcode 40 题
给出一个数组和目标值,求数组元素和等于目标值的可能组合
https://leetcode.com/problems/combination-sum-ii/description/

想了好久也不出怎么用动态规划做...

geelaw

2018 年 8 月 7 日

@streamo #10 是不是要输出具体方案和是不是背包问题没有必然联系。解决背包问题的动态规划算法可以加上对方案的记录。

wkan

2018 年 8 月 7 日

点最便宜的那个，多点几份是最接近的

lychnis

2018 年 8 月 7 日

点外卖你这样算出来的你愿意吃吗。。。

streamo

2018 年 8 月 7 日

@geelaw 想了下觉得你说的对，求具体方案不用 DP 成了我惯性思维了。

murmur

2018 年 8 月 7 日

@waiaan 没有算法怎么谈需求
饿了么这种他为了刺激你消费绝对不会给你最优的背包
你点一个他就会提示下一档优惠是多少
不断刺激你加东西

waiaan

2018 年 8 月 7 日

@murmur
@lychnis
只是单纯讨论这个问题的思路

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.