背景
业务中有一个功能,可以使用优惠券抵扣字数,优惠券面额有 300 字、500 字和 800 字,张数随机。在用户下单的时候需要为其自动推荐最佳优惠券组合,同时为了保证优惠券不浪费,最多只能溢出小于 300 字。
例如 900 字的订单,有 2 张 800 字优惠券,若全部使用,则会浪费 700 字,对用户体验不好。对于这种情况,只为用户自动选择 1 张 800 字的优惠券即可。
那么这个问题可以抽象为一个有条件限制的多重背包问题。
题目描述
你有若干张优惠券,每张优惠券可以抵扣一定的字数,规则如下:
优惠券面额为300、500、800,每种张数有限
每次用户选择一个目标字数target(为100的整数倍)
请你从宜有的优惠券中选出若干张,使得总字数sum满足
sum >= target (必须覆盖目标字数)
sum - target < 300(溢出必须严格小于300,即最小优惠券面额)
如果找不到满足上述条件的组合,退而求其次,返回一个 sum <= target的组合,要求它尽可能接近target。
如果仍然无法组成任意组合,则返 ...