优惠券叠加，得出优惠最大的组合情况

Question

波波老师 你好，我工作中遇到这么一个事情，是关于优惠券叠加使用的问题，目的是帮助用户选择出一组给予最大优惠的券组合.
我分析了下，券组合的确是存在子问题的，但是子问题的计算结果是有后效性的，比如A，B两张券种，无论先用了那张，对另外一张券的门槛限制就可能会有影响，还有一个关键的问题，选择顺序对01背包是没有影响的，但是优惠券来说，使用顺序至关重要，像类似情况只能用枚举法么？还是说也是可以使用动态规划的去实现的？希望波波老师帮我分析下.感谢?

Answer 1

liuyubobobo 2020-08-12 19:00:36

你对问题的描述我还是没有理解不同优惠券的门槛限制或者顺序关系对解的影响是怎样的。但是如果你确定是存在后效性的，且优惠券的数量并不多的话（10个左右的话），穷举是完全没有问题的。

如果你确定存在后效性的话，另一个方案是使用诸如贪心的方式，给出一个近似解。实际上，在现实中，很多情况下不需要最优解，因为给出最优解的代价太高，而其实并没有必要。比如在你的场景中，建议优惠券使用组合，比一定一定是最you2的。

近似解的给出，除了使用贪心，更加精细化一些，可以使用启发式的方式做搜索，然后给一个最低运算时间，最后算法得到的解是在这个时间内算出来的最优解。如果启发函数设计的足够好，大部分时间给出的解很可能也是最优解。

继续加油！：）

• 提问者 JasonC3 #1

  明白了，感谢波波老师的解答，另外在我在问题中没有表述清楚后效果性以及券使用顺序对计算的影响，我在重新表述下
  比如两张券，A券(满70减50),B券(满40减-35)，C券(满40-20)，其中有商品E(单价为100元)能够使用这三张券，我们在使用时暴力组合就会有：ABC，ACB，BAC，BCA，CAB，CBA，我们可以看到，如果我们优先使用了B之后，那E的价格变成了65，显然，他是无法使用A的，但是如果先使用了A，E此时的价格变为50，那么可以使用B，也就是说，由于券使用顺序的不同，会导致计算同一个券时，结果也是不一致的，我理解 这在使用动态规划中，显然无法满足子问题最优解以无后效性的约束

• liuyubobobo 回复 提问者 JasonC3 #2

  你的理解是对的。但是对于你举的这个例子，是满足贪心性质的。但我不确定是不是你们的所有优惠券的设计都满足贪心性质。因此要具体问题具体分析。