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

[tqz]

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

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

不好意思我没有描述清楚，我再描述一下：

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

输入的是 double[] weight，他的长度未知，输出的是一个集合，里面存储着可行的方案

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

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));
    }
}

这帖子已经过期了，感谢各位的帮助

[xuekedou]

没看懂，优惠是指包邮？

[lix7]

猛的一看哈，排序然后滑动窗口就行了吧

[yesterdaysun]

没懂, "全场商品 4 件，10kg 内包邮", 为了包邮, 那不就是一件件买最划算? 但是标题的满减又是怎么回事?

[Shaw314]

回溯吧，我看里面还有重复的 那应该每件商品只能选一次，排个序，然后回溯跳过重复的，参考 leetcode40 题
https://leetcode-cn.com/problems/combination-sum-ii/

[flavoury]

听起来像是背包问题，动态规划，看看这个？
https://wongdean.github.io/2019/09/26/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/

[las917vki]

10kg 内包邮
那最划算不是全部一件件买吗。。。

[poisedflw]

@las917vki 鬼才

[AX5N]

排列组合，求出所有组合，然后再筛选结果。

[lonenol]

感觉是满四件，且在 10kg 内包邮吧。。要是求所有可能的组合感觉排序后回溯吧，可以参考上边说的 40 题，如果一件商品可以买多件，可以参考 39

[tqz]

不好意思我没有描述清楚，我再描述一下：
店铺做活动，全场商品需最少满 4 件，且重量在 10kg 内则包邮，超过了则自己付全部的运费。
现在需要你一次性凑尽量多的货物以尽可能享受到优惠。 （不可以一件一件的买）
知道的是一系列商品的质量，以 kg 为单位， 例如：[0.34, 3, 2, 34.3, 5, 5]，可以给出的凑单方案：[3, 2, 5], [5, 5]。

输入的是 double[] weight，他的长度未知，输出的是一个集合，里面存储着可行的方案

[Asuka3]

排序后 建立线段树 逐步压缩区间求线段和，复最坏情况下杂度好像是 N×N×logN，额有点太高了……

[Gatsbywl]

[3, 2, 5], [5, 5] 不是不满足最少 4 件的要求吗？？