V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
tqz
V2EX  ›  程序员

[算法求助] 满减优惠怎么做

  •  
  •   tqz · 2020-02-03 15:02:05 +08:00 · 3085 次点击
    这是一个创建于 1760 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我面试遇到一个题,不会解。。求助大佬指点一下,题目如下

    店铺做活动,全场商品 4 件,10kg 内包邮。 现在需要凑到 10kg 的重量以尽可能享受到优惠。 知道的是一系列商品的质量,以 kg 为单位, 例如:[0.34, 3, 2, 34.3, 5, 5],可以给出的凑单方案:[3, 2, 5], [5, 5]。

    第 1 条附言  ·  2020-02-03 21:53:08 +08:00
    不好意思我没有描述清楚,我再描述一下:

    店铺做活动,全场商品需最少满 4 件,且重量在 10kg 内则包邮,超过了则自己付全部的运费。
    现在需要一次性凑尽量多的货物以尽可能享受到优惠。 (不可以一件一件的买)
    知道的是一系列商品的质量,以 kg 为单位, 例如:[0.34, 3, 2, 34.3, 5, 5],可以给出的凑单方案如:[3, 2, 5], [5, 5]。

    输入的是 double[] weight,他的长度未知,输出的是一个集合,里面存储着可行的方案
    第 2 条附言  ·  2020-02-04 13:06:01 +08:00

    各位老哥,我看了评论自己实现了一个,菜鸟献丑了,不知道各位怎么看我这种实现方式

    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class 满减优惠 {
    
        public static List<List<Double>> getWays(double[] weights, double limit) {
            List<List<Double>> ans = new ArrayList<>();
            List<Double> tmp = new ArrayList<>();
            // 我认为排个序后更有利于递归处理
            Arrays.sort(weights);
            doCalculate(ans, tmp, weights, limit);
            return ans;
        }
    
        public static void doCalculate(List<List<Double>> ans, List<Double> tmp,
                                       double[] weights, double limit) {
            // 递归结束的条件
            if (limit < 0.0) { // 偷个懒,虽然我知道不能用 = 号判断浮点数是否相等
                return;
            }
            if (noRemainCapacity(weights, limit)) {
                ans.add(new ArrayList<>(tmp));
                return;
            }
            // 由于同一个商品可以添加多次,所以不设置去重操作
            for (int i = 0; i < weights.length; i++) {
                tmp.add(weights[i]);
                doCalculate(ans, tmp, weights, limit - weights[i]);
                tmp.remove(tmp.size() - 1);
            }
        }
    
        /**
         *  该方法的意思就是检查当前剩余购物的空间,能否再装点物品进去
         *  实现方式就是检查剩余空间能否装下最小的物品
         * @param weights 物品重量数组
         * @param limit 剩余可以装的重量
         * @return 若不能装了返回 true
         */
        public static boolean noRemainCapacity(double[] weights, double limit) {
            double min = Double.MAX_VALUE;
            for (int i = 0; i < weights.length; i++) {
                if (weights[i] < min) {
                    min = weights[i];
                }
            }
            return limit < min ? true : false;
        }
    
        public static void main(String[] args) {
            double[] weights = {3.4, 3.0, 2.0, 1.3, 4.5, 5.0};
            double limit = 11.0;
            List<List<Double>> ans = getWays(weights, limit);
            ans.forEach(e -> System.out.println(e));
        }
    }
    
    
    第 3 条附言  ·  2020-02-05 17:08:16 +08:00
    这帖子已经过期了,感谢各位的帮助
    12 条回复    2020-02-04 18:45:48 +08:00
    xuekedou
        1
    xuekedou  
       2020-02-03 15:09:59 +08:00
    没看懂,优惠是指包邮?
    lix7
        2
    lix7  
       2020-02-03 15:18:10 +08:00
    猛的一看哈,排序然后滑动窗口就行了吧
    yesterdaysun
        3
    yesterdaysun  
       2020-02-03 15:19:21 +08:00
    没懂, "全场商品 4 件,10kg 内包邮", 为了包邮, 那不就是一件件买最划算? 但是标题的满减又是怎么回事?
    Shaw314
        4
    Shaw314  
       2020-02-03 15:31:38 +08:00
    回溯吧,我看里面还有重复的 那应该每件商品只能选一次,排个序,然后回溯跳过重复的,参考 leetcode40 题
    https://leetcode-cn.com/problems/combination-sum-ii/
    flavoury
        5
    flavoury  
       2020-02-03 16:05:39 +08:00
    听起来像是背包问题,动态规划,看看这个?
    https://wongdean.github.io/2019/09/26/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/
    las917vki
        6
    las917vki  
       2020-02-03 16:19:33 +08:00   ❤️ 3
    10kg 内包邮
    那最划算不是全部一件件买吗。。。
    poisedflw
        7
    poisedflw  
       2020-02-03 16:30:23 +08:00
    @las917vki 鬼才
    AX5N
        8
    AX5N  
       2020-02-03 17:33:50 +08:00
    排列组合,求出所有组合,然后再筛选结果。
    lonenol
        9
    lonenol  
       2020-02-03 17:40:55 +08:00
    感觉是满四件,且在 10kg 内包邮吧。。要是求所有可能的组合感觉排序后回溯吧,可以参考上边说的 40 题,如果一件商品可以买多件,可以参考 39
    tqz
        10
    tqz  
    OP
       2020-02-03 21:49:59 +08:00
    不好意思我没有描述清楚,我再描述一下:
    店铺做活动,全场商品需最少满 4 件,且重量在 10kg 内则包邮,超过了则自己付全部的运费。
    现在需要你一次性凑尽量多的货物以尽可能享受到优惠。 (不可以一件一件的买)
    知道的是一系列商品的质量,以 kg 为单位, 例如:[0.34, 3, 2, 34.3, 5, 5],可以给出的凑单方案:[3, 2, 5], [5, 5]。

    输入的是 double[] weight,他的长度未知,输出的是一个集合,里面存储着可行的方案
    Asuka3
        11
    Asuka3  
       2020-02-04 10:47:30 +08:00 via iPhone
    排序后 建立线段树 逐步压缩区间求线段和,复最坏情况下杂度好像是 N×N×logN,额有点太高了……
    Gatsbywl
        12
    Gatsbywl  
       2020-02-04 18:45:48 +08:00
    [3, 2, 5], [5, 5] 不是不满足最少 4 件的要求吗??
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1025 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 20:38 · PVG 04:38 · LAX 12:38 · JFK 15:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.