讨论/技术交流/请教一个优惠券最优算法/
请教一个优惠券最优算法

各位大佬好:
本人现在遇到一个优惠券最优算法问题,不知道大家有没有什么建议,在此先谢过了。

主要条件我列在下面:

  1. 优惠券分两大类,平台券和推广券,记为cp 和 ct
  2. 每一类券都有三种表现形式:满减(比如满100减10),折扣(比如打八折),现金券(直接可用某一额度的券,比如50元现金券)
  3. 每个商品最多使用平台券和推广券各一张
  4. 对于一个商品而言,平台券优先于推广券,一个商品可以单独只用一个cp或者一个ct,或者先用cp后用ct,但是不能先用ct再用cp
  5. 一个订单最多使用5张券
  6. 要求最终优惠力度最大

拿到这个问题,本来以为是背包或者动态规划问题,但是发现里面的相互依赖和互斥比较严重,没有严格的重叠子问题。比如:

商品A 50元 B 20元 C 30元 , 平台券CP1 是满100-30,可以用于商品ABC, 平台券CP2 是满50 - 10,可用于商品BC, 还有一个推广券CT1 可用于商品A是 折扣券,打8折

如果使用CP1,那么总金额变为70(均摊后A为50 - 10 = 40, B为10,C为20),然后再给A使用推广券CT1,也就是40打8折,变为32,最后总金额为102

如果使用CP2,总金额变为90(A还是50,B变为15,C变为25),然后再给A的50打8折后是40,最终金额是40 + 15 + 25 = 80

有同一商品互斥情况如下:
商品A 80 商品B 50 商品C 20 ,平台券CP1为8折,可用于ABC,平台券CP2为满100减50,可用于商品AC,还有平台券CP3为满50减10,可用于商品BC

如果使用CP1,也就是ABC一起打8折,那么A=64,B=40,C=16,剩下的CP2和CP3都无法使用,因为同一个商品只能同时使用一张平台券,最终结果是120

如果使用CP2,就是AC使用满100-50,均摊后A=55,C=-5(纳尼?),这里又是一个bug,不可能是负的,所以是A=50,C=0。这个时候还能用CP1,为什么呢,因为CP1可以作用与ABC,这里还有个B可以打折,就是40,最终结果是50 + 40 + 0 = 90。当然,也可以再用CP1之后再用CP3,可以用于B,他是满50-10,在这里结果也是50 - 10 = 40,所以最终结果一样,都死90

再比如:商品A价值200,有CP1为满200-30,有CP2为打8折,有CT1为满180减100。这个时候不论使用CP1还是CP2都导致无法使用CT1,所以直接不用平台券而用推广券CT1,最终结果就是200-100=100

我总结下难点:

券互斥问题
顺序问题,不同的使用顺序对后续的使用情况,还有金额都有影响
现在能想到的做法就是遍历,随机取5张,分别看5张顺序不同使用排序后的情况,这就是组合Cn 5之后还要再乘以5的全排列也就是120,当用户有很多券的时候,系统直接down。。。

求大佬给出点思路,谢谢!!!

6

回溯打印所有排列组合
维持的visited可以继续计算后续产品的排列组合

private static class Solution {
        private int len;
        private char[] array;
        private boolean[] visited;

        private Solution(char[] array) {
            this.len = array.length;
            this.array = array;
            this.visited = new boolean[array.length];
        }

        private void solve() {
            dfs(0, 0, new char[len]);
        }

        private void dfs(int i, int st, char[] chars) {
            if (i == len) System.out.println(new String(chars));
            else {
                while (st < len && visited[st]) st++;
                if (st == len) return;
                visited[st] = true;
                chars[i] = array[st];

                //continue
                dfs(i + 1, 0, chars);
                //recall
                visited[st] = false;
                dfs(i, st + 1, chars);
            }
        }
    }
展开全部 18 讨论