优惠券叠加，得出优惠最大的组合情况
来源：9-5 0-1背包问题
JasonC3
2020-08-12
波波老师 你好，我工作中遇到这么一个事情，是关于优惠券叠加使用的问题，目的是帮助用户选择出一组给予最大优惠的券组合.
我分析了下，券组合的确是存在子问题的，但是子问题的计算结果是有后效性的，比如A，B两张券种，无论先用了那张，对另外一张券的门槛限制就可能会有影响，还有一个关键的问题，选择顺序对01背包是没有影响的，但是优惠券来说，使用顺序至关重要，像类似情况只能用枚举法么？还是说也是可以使用动态规划的去实现的？希望波波老师帮我分析下.感谢?
写回答
1回答
-
你对问题的描述我还是没有理解不同优惠券的门槛限制或者顺序关系对解的影响是怎样的。但是如果你确定是存在后效性的，且优惠券的数量并不多的话（10个左右的话），穷举是完全没有问题的。
如果你确定存在后效性的话，另一个方案是使用诸如贪心的方式，给出一个近似解。实际上，在现实中，很多情况下不需要最优解，因为给出最优解的代价太高，而其实并没有必要。比如在你的场景中，建议优惠券使用组合，比一定一定是最you2的。
近似解的给出，除了使用贪心，更加精细化一些，可以使用启发式的方式做搜索，然后给一个最低运算时间，最后算法得到的解是在这个时间内算出来的最优解。如果启发函数设计的足够好，大部分时间给出的解很可能也是最优解。
继续加油！：）
122020-08-12
相似问题