问一个算法的思路

[waiaan]

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

[wingkou]

这不就是线性规划吗？

[timboy]

背包问题？

[murmur]

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

[dingyaguang117]

背包问题

[enenaaa]

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

[waiaan]

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

[rabbbit]

允许重复点同一个菜吗?

[geelaw]

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

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

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

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

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

[jasonMakarov]

KNN 考虑下吧

[streamo]

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

[waiaan]

@rabbbit 当然可以

[rabbbit]

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

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

[geelaw]

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

[wkan]

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

[waiaan]

@rabbbit 差不多是这个意思了

[lychnis]

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

[streamo]

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

[murmur]

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

[murmur]

*更正：没有需求怎么谈算法

[waiaan]

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