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

[tqz]

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

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

[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 件的要求吗？？