问一个算法的思路

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐关注

› Meteor

› JSLint - a JavaScript code quality tool

› jsFiddle

› D3.js

› WebStorm

推荐书目

› JavaScript 权威指南第 5 版

› Closure: The Definitive Guide

这是一个创建于 2301 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

算法

满减

点菜

外卖

34 条回复 • 2018-08-08 07:38:53 +08:00

wingkou

2018-08-07 11:17:09 +08:00 via Android

这不就是线性规划吗？

timboy

2018-08-07 11:37:43 +08:00

背包问题？

murmur

2018-08-07 11:40:05 +08:00

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

dingyaguang117

2018-08-07 11:42:04 +08:00

背包问题

enenaaa

2018-08-07 11:42:15 +08:00

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

waiaan

2018-08-07 11:45:04 +08:00 via Android

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

rabbbit

2018-08-07 11:59:15 +08:00

允许重复点同一个菜吗?

geelaw

2018-08-07 12:00:55 +08:00

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

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

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

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

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

jasonMakarov

2018-08-07 12:01:34 +08:00

KNN 考虑下吧

streamo

2018-08-07 12:02:29 +08:00

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

waiaan

2018-08-07 12:04:34 +08:00 via Android

@rabbbit 当然可以

rabbbit

2018-08-07 12:07:57 +08:00

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

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

geelaw

2018-08-07 12:08:15 +08:00

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

wkan

2018-08-07 12:10:41 +08:00 via Android

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

waiaan

2018-08-07 12:17:15 +08:00 via Android

@rabbbit 差不多是这个意思了

lychnis

2018-08-07 12:20:30 +08:00 via Android

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

streamo

2018-08-07 12:21:54 +08:00

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

murmur

2018-08-07 12:23:48 +08:00

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

murmur

2018-08-07 12:24:01 +08:00

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

waiaan

2018-08-07 12:25:03 +08:00 via Android

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

shakespaces

2018-08-07 12:27:24 +08:00 via Android

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

lychnis

2018-08-07 12:29:09 +08:00 via Android

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

rabbbit

2018-08-07 12:29:41 +08:00

搞错了,应该是和 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

2018-08-07 12:32:16 +08:00

waiaan

2018-08-07 12:38:21 +08:00 via Android

@rabbbit 好

ppyybb

2018-08-07 12:44:40 +08:00 via iPhone

如果要求用户至少花费 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)