问一个算法的思路

[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
只是单纯讨论这个问题的思路

[shakespaces]

对于外卖这种，一个店里最多也就几十种菜品，直接一个暴力就结束了😂

[lychnis]

@waiaan 上面有人说了 leetcode n sum 原题。。 但你这个场景就不能硬套

[rabbbit]

搞错了,应该是和 39 题比较像,因为可以重复点菜.

暴力搜索...
```
var combinationSum = function (candidates, target) {
let min = Infinity;
let solution = [];
len = candidates.length;
let callback = function (i, target, arr) {
if (target <= 0 && Math.abs(target) <= min) {
if (Math.abs(target) === min) {
solution.push(arr.slice());
} else {
solution = [arr.slice()];
}
min = Math.abs(target);

} else if (target > 0) {
while (i < len) {
arr.push(candidates[i]);
callback(i, target - candidates[i], arr);
arr.pop();
i++;
}
}
}
callback(0, target, []);
return [min, solution];
};

console.log(combinationSum([1], 2));
// ​​​​​[ 0, [ [ 1, 1 ] ] ]​​​​​
console.log(combinationSum([1, 2], 3.1));
// ​​​​​[ 0.8999999999999999,​​​​​ [ [ 1, 1, 1, 1 ], [ 1, 1, 2 ], [ 2, 2 ] ] ]​​​​​
console.log(combinationSum([1, 2, 3], 5));
// ​​​​​[ 0,​​​​​ [ [ 1, 1, 1, 1, 1 ],​​​​​ [ 1, 1, 1, 2 ],​​​​​ [ 1, 1, 3 ],​​​​​ [ 1, 2, 2 ],​​​​​ [ 2, 3 ] ] ]​​​​​
```

[rabbbit]

[waiaan]

@rabbbit 好

[ppyybb]

如果要求用户至少花费 k 元,那么可以提供一个思路:
假设不妨设一共 N 个菜,设状态 dp[i][S] 为处理了前 i 个菜,一共点了 S 的价格的状态(0 表示不存在这个状态,1 表示存在这个状态)
先不考虑满减,显然 dp[i + 1][S + price[i + 1]]
dp[i+1][S] = dp[S]
所以 dp[N-1]表示所有菜都考虑了的情况,那么考虑满减 dp[N-1][S] - discount (如果有多个满减,就找最近点那一个)
结果就是最小的那个

这种情况如果 S 的总价格不是很大,那么状态不会很多(我们可以假设用户不会点超过 1000 的外卖,S <= 1000,如果超过一般都会超过最大的满减上限了)
也就是搜索一个 N * S 的状态空间就可以解决

优化空间: 显然 dp[i]只依赖 dp[i-1],所以两个一维数组就可以解决
剪枝: 保留当前最小的 S - discount,那么我们可以判断从当前状态出发是否存在更小的可能,这里分类讨论可能的 discount
缓存: 从业务考虑,我们完全可以先计算好前 100 个状态,然后需要的时候直接从缓存好的状态开始计算起(时间和空间的 tradeoff)

[Biwood]

我想说，抛开技术不谈，这类满减活动多半只是为了让你多消费而已。

判断是否真的优惠只有一个办法，首先别看优惠活动，先选好所有你想要的东西，然后再看优惠活动规则。如果参与优惠比当前订单金额小，那么就是值得的。如果参与优惠后，金额比之前增多，说明你只是用“看起来更便宜”的价格买了你不需要的东西而已。

[MiffyLiye]

暴力解法有穷举。
半暴力解法有 backtracking 和 branch and bound。
随便加点额外的约束，例如需要包含特定种类、限定特定种类的数量，搜索过程就能快很多。

[ryuzaki113]

说个题外话，外卖满减再多不如去店里吃

[zhzer]

动态规划

[PulpFunction]

1。先拿到所有的优惠满减信息
2。你得有一个预计花钱的参数吧
3。把 1 里面的价格相减，算出每一个优惠信息的低消
4。排序 选择一个比预计花钱少的 选一个比预计花钱多的；或者多选点 反正就是几个下标的问题

[PulpFunction]

5。凑钱 选主食和配菜（ 0.获取主食套餐与小吃） 超出预期越少的越实惠，有时候多一点更实惠。。

[stephenyin]

@ryuzaki113 #29 绝大多数外卖满减+平台补贴后都比店里便宜.

[tt67wq]

有个比较经典的背包问题，跟这个差不多吧