V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
waiaan
V2EX  ›  JavaScript

问一个算法的思路

  •  
  •   waiaan · 2018-08-07 11:15:22 +08:00 · 6096 次点击
    这是一个创建于 2299 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    34 条回复    2018-08-08 07:38:53 +08:00
    wingkou
        1
    wingkou  
       2018-08-07 11:17:09 +08:00 via Android
    这不就是线性规划吗?
    timboy
        2
    timboy  
       2018-08-07 11:37:43 +08:00
    背包问题?
    murmur
        3
    murmur  
       2018-08-07 11:40:05 +08:00
    需求在哪里呢?
    点餐不是按喜欢吃和吃多少点么
    满 35 减 24 等你点了结账就发现会多出几块钱的饭盒费和派送费
    dingyaguang117
        4
    dingyaguang117  
       2018-08-07 11:42:04 +08:00
    背包问题
    enenaaa
        5
    enenaaa  
       2018-08-07 11:42:15 +08:00
    从全排列开始。逐个条件裁剪掉不必要的路径。再以动态规划策略利用到历史步骤的结果。
    waiaan
        6
    waiaan  
    OP
       2018-08-07 11:45:04 +08:00 via Android
    @murmur 不是,只是偶然想到这个问题,跟具体点餐的事情没关系。
    rabbbit
        7
    rabbbit  
       2018-08-07 11:59:15 +08:00
    允许重复点同一个菜吗?
    geelaw
        8
    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
        9
    jasonMakarov  
       2018-08-07 12:01:34 +08:00
    KNN 考虑下吧
    streamo
        10
    streamo  
       2018-08-07 12:02:29 +08:00
    因为你要求具体方案所以不是背包。比较容易想到的办法是用 DFS 求排列组合然后在结果集里挑。
    waiaan
        11
    waiaan  
    OP
       2018-08-07 12:04:34 +08:00 via Android
    @rabbbit 当然可以
    rabbbit
        12
    rabbbit  
       2018-08-07 12:07:57 +08:00
    这个比较像 leetcode 40 题
    给出一个数组和目标值,求数组元素和等于目标值的可能组合
    https://leetcode.com/problems/combination-sum-ii/description/

    想了好久也不出怎么用动态规划做...
    geelaw
        13
    geelaw  
       2018-08-07 12:08:15 +08:00
    @streamo #10 是不是要输出具体方案和是不是背包问题没有必然联系。解决背包问题的动态规划算法可以加上对方案的记录。
    wkan
        14
    wkan  
       2018-08-07 12:10:41 +08:00 via Android
    点最便宜的那个,多点几份是最接近的
    waiaan
        15
    waiaan  
    OP
       2018-08-07 12:17:15 +08:00 via Android
    @rabbbit 差不多是这个意思了
    lychnis
        16
    lychnis  
       2018-08-07 12:20:30 +08:00 via Android
    点外卖 你这样算出来的你愿意吃吗。。。
    streamo
        17
    streamo  
       2018-08-07 12:21:54 +08:00
    @geelaw 想了下觉得你说的对,求具体方案不用 DP 成了我惯性思维了。
    murmur
        18
    murmur  
       2018-08-07 12:23:48 +08:00
    @waiaan 没有算法怎么谈需求
    饿了么这种他为了刺激你消费绝对不会给你最优的背包
    你点一个他就会提示下一档优惠是多少
    不断刺激你加东西
    murmur
        19
    murmur  
       2018-08-07 12:24:01 +08:00
    *更正:没有需求怎么谈算法
    waiaan
        20
    waiaan  
    OP
       2018-08-07 12:25:03 +08:00 via Android
    @murmur
    @lychnis
    只是单纯讨论这个问题的思路
    shakespaces
        21
    shakespaces  
       2018-08-07 12:27:24 +08:00 via Android
    对于外卖这种,一个店里最多也就几十种菜品,直接一个暴力就结束了😂
    lychnis
        22
    lychnis  
       2018-08-07 12:29:09 +08:00 via Android
    @waiaan 上面有人说了 leetcode n sum 原题。。 但你这个场景就不能硬套
    rabbbit
        23
    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
        24
    rabbbit  
       2018-08-07 12:32:16 +08:00
    waiaan
        25
    waiaan  
    OP
       2018-08-07 12:38:21 +08:00 via Android
    @rabbbit
    ppyybb
        26
    ppyybb  
       2018-08-07 12:44:40 +08:00 via iPhone   ❤️ 1
    如果要求用户至少花费 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
        27
    Biwood  
       2018-08-07 12:51:52 +08:00
    我想说,抛开技术不谈,这类满减活动多半只是为了让你多消费而已。

    判断是否真的优惠只有一个办法,首先别看优惠活动,先选好所有你想要的东西,然后再看优惠活动规则。如果参与优惠比当前订单金额小,那么就是值得的。如果参与优惠后,金额比之前增多,说明你只是用“看起来更便宜”的价格买了你不需要的东西而已。
    MiffyLiye
        28
    MiffyLiye  
       2018-08-07 13:14:42 +08:00
    暴力解法有穷举。
    半暴力解法有 backtracking 和 branch and bound。
    随便加点额外的约束,例如需要包含特定种类、限定特定种类的数量,搜索过程就能快很多。
    ryuzaki113
        29
    ryuzaki113  
       2018-08-07 14:04:42 +08:00
    说个题外话,外卖满减再多不如去店里吃
    zhzer
        30
    zhzer  
       2018-08-07 14:32:12 +08:00
    动态规划
    PulpFunction
        31
    PulpFunction  
       2018-08-07 17:08:56 +08:00
    1。先拿到所有的优惠满减信息
    2。你得有一个预计花钱的参数吧
    3。把 1 里面的价格相减,算出每一个优惠信息的低消
    4。排序 选择一个比预计花钱少的 选一个比预计花钱多的;或者多选点 反正就是几个下标的问题
    PulpFunction
        32
    PulpFunction  
       2018-08-07 17:12:19 +08:00
    5。凑钱 选主食和配菜( 0.获取主食套餐与小吃) 超出预期越少的越实惠,有时候多一点更实惠。。
    stephenyin
        33
    stephenyin  
       2018-08-07 17:54:27 +08:00
    @ryuzaki113 #29 绝大多数外卖满减+平台补贴后都比店里便宜.
    tt67wq
        34
    tt67wq  
       2018-08-08 07:38:53 +08:00 via Android
    有个比较经典的背包问题,跟这个差不多吧
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2903 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 03:09 · PVG 11:09 · LAX 19:09 · JFK 22:09
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.