有限预算分配下的01背包问题

有限预算的权益分配本质上是个升级版的背包问题。假设总预算为$C$，用户$i$在券$j$下的核销率是$p_{ij}$，发券面额是$c_{ij}$，我们的求解目标是总预算约束下的订单最大化：

$$max \sum_{i,j} x_{ij} p_{ij} \\ \begin{aligned} \text { s.t. } x_{ij} & \in \{0, 1\} \\ \sum_{j} x_{ij} &= 1 \\ \sum_{i,j} x_{ij} c_{ij} &\leq C \\ \end{aligned}$$

将上述业务问题抽象成01背包问题就是，在背包容量限制下的物品价值最大化。但传统的背包问题对应的是给同一个用户发多张券，而营销场景则是给多个用户分别只发一张券，相当于二维化传统背包问题了。

定义$dp[i][j][k]$为在预算$k$下给用户$i$发放券$j$后的累计最大订单量，那么动态转移方程如下：

$$dp[i][j][k] = max(dp[i-1][:J][:k])+p_{ij}$$

其中$J$表示券的总数，是个枚举值。

代码示例：

def max_value(users_coupons, C):
    # 用户数
    user_num = len(users_coupons)
    # 券数
    coupon_num = len(users_coupons[0])

    dp = []
    for i in range(user_num):
        tmp = [[float("-inf")] * (C + 1) for _ in range(coupon_num)]
        dp.append(tmp)

    # dp[i][j][k]：在预算k下，给用户i发放券j下的的累计最大订单
    # 第1个用户初始化
    for j in range(coupon_num):
        for k in range(1, C + 1):
            if users_coupons[0][j][0] <= k:
                dp[0][j][k] = users_coupons[0][j][1]

    for i in range(1, user_num):
        for j in range(coupon_num):
            for k in range(1, C + 1):
                # 发券成本，核销率
                cost, cvr = users_coupons[i][j]
                # 说明此刻预算能给用户i发放券j
                if cost <= k:
                    # 发放券j后，剩余的预算
                    gap = k - cost
                    # 遍历上一个用户的所有可能发放券，获取剩余预算下的最大订单量
                    for prev_j in range(coupon_num):
                        prev_max_value = max(dp[i - 1][prev_j][:gap + 1])
                        dp[i][j][k] = max(prev_max_value + cvr, dp[i][j][k])

    ret = float("-inf")
    for j in range(coupon_num):
        ret = max(max(dp[user_num - 1][j]), ret)

    return ret


if __name__ == "__main__":
    users_coupons = [
        [[2, 0.3], [4, 0.6], [1, 0.2]],
        [[5, 0.1], [3, 0.8], [2, 0.6]],
        [[7, 0.3], [8, 1], [3, 0.9]]
    ]
    C = 15
    ret = max_value(users_coupons, C)
    print("max accumulate cvr: {}".format(ret))

备注：上述代码实现的时空复杂度过高，一天的预算都有几个亿，不可能初始化这么大的数组，且寻找最优解耗时也长。业界对于此营销问题的解决方案都是走运筹，具体见：线上运筹优化公式推导