问一个算法的思路

[waiaan]

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

[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]

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