一个思考题

yuanfan

下面本楼主编了一个表，其中 id 表示一行记录的唯一标识，customer_id 表示一个客户的唯一标识，policy_id 表示一次购买记录的唯一标识，product 表示一次购买记录中具体购买的产品（可重复购买），fee 表示每次购买一个产品的购买金额（同种产品可用不同金额购买多次）。

已知一个客户购买一个产品的累计总金额超过50可以得到一个函件，若是多次购买累积金额均超过50可能会得到多个函件，但是函件数量与购买记录有特别的绑定关系，一次购买记录最多只能对应得到一个函件。

比如同一客户同一次购买记录中买了三次产品B，金额分别是71/31/21，虽然总金额加起来共123，但是只能得到1个函件。
比如一个客户购买同种产品有4次购买记录，金额分别是41、31、21、11，那么按照41+11、31+21均会累积超过50，那么会得到2个函件。

求：每个客户每种产品分别能得到多少函件？（PS虽然只编了十几条数据，但是可以想象要解决的问题是由无数条数据组成的。）

```
data <- data.frame(
  id = c(1:14),
  customer_id = c(rep(1, 2), rep(2, 3), rep(3, 5), rep(4, 4)),
  policy_id = c(123:124, rep(125, 3), 126:134),
  product = c(rep('A', 2), rep('B', 3), rep('C', 4), 'D', rep('E', 4)),
  fee = c(51, 51, 71, 31, 21, 28, 28, 28, 20, 51, 41, 31, 21, 11))
head(data, 14)
```
    id customer_id policy_id product fee
1   1           1       123       A  51
2   2           1       124       A  51
3   3           2       125       B  71
4   4           2       125       B  31
5   5           2       125       B  21
6   6           3       126       C  28
7   7           3       127       C  28
8   8           3       128       C  28
9   9           3       129       C  20
10 10           3       130       D  51
11 11           4       131       E  41
12 12           4       132       E  31
13 13           4       133       E  21
14 14           4       134       E  11

按照上面编造的数据，客户1会得到2个函件，客户2得到1个函件，客户3得到2个函件，客户4得到2个函件。

fenguoerbian

规则还是不够清楚诶：触发了函件之后，当前的用于触发函件的累积金额怎么算？是减去50，还是对50取余，还是直接清零？
顺着你的例子，这三种情况对应着下次购买至少花费1元，27元，还是50元才能触发函件？

yuanfan

fenguoerbian
抱歉，我这就再多叨几句。按照一次购买记录最多只能对应得到一个函件的条件，假如一次购买记录已经被触发了一个函件，那么此购买记录中超过50的部分可算是清零了。

上面的例子中，customer_id 为1的客户会得到2个函件，客户2会得到1个函件，客户3会得到2个函件。

yuanfan

fenguoerbian

还有一件小事，我在描述问题的时候只提到了金额的数字，没有提过单位，为撒你第一反应是“元”而不是“万元”呢？

fenguoerbian

恩……说实话我只想到for循环伺候了😂

yuanfan

fenguoerbian
嗯，咋循环呢？说实话，我一点思路都无，我同事小花想的思路是：先把只会有一个函件的情况找出来，然后去掉这部分，继续找会有2个函件的情况……

fenguoerbian

yuanfan
这……规则都已经明确了那就把规则翻译给电脑听就行了啊。

先把金额根据客户、商品、购买记录进行分组汇总，得到每个客户、每样商品，按订单顺序的一个花费金额序列

data1 <- data %>%
    group_by(customer_id, product, policy_id) %>%
    summarise(amount = sum(fee)) %>%
    ungroup()

然后根据你给的规则写个函数，输入的就是一个每次的花费金额的序列，返回每次是否要发送函件

My_Deliver <- function(amount_vec){
    res <- rep(FALSE, length(amount_vec))    # 初始化为每次均不发送
    current_cum_amount <- 0    # 记录当前累积金额
    for(i in seq_along(res)){
        current_cum_amount <- current_cum_amount + amount_vec[i]
        if(current_cum_amount >= 50){
            # 达到50，则发送函件，并将当前累积金额清零
            res[i] <- TRUE
            current_cum_amount <- 0
        }
    }
    return(res)
}

于是就可以得到每个人在每件商品上的购买记录所对应的发送情况了

data1 %>%
    group_by(customer_id, product) %>%
    mutate(deliver = My_Deliver(amount))

yuanfan

fenguoerbian

唔，但是还有一个问题，比如一个人购买同种产品，有4次不同购买记录，金额分别是41、31、21、11，此人实际上会得到2个函件，分别是41+11、31+21。抱歉，是我前面举例子编的数据太容易了，没有把这个本来就存在的问题编进去。

```
data <- data.frame(
  id = c(1:4),
  customer_id = c(rep(4, 4)),
  policy_id = c(131:134),
  product = c(rep('A', 4)),
  fee = c(41, 31, 21, 11))
```
  id customer_id policy_id product fee
1  1           4       131       A  41
2  2           4       132       A  31
3  3           4       133       A  21
4  4           4       134       A  11

按照你写的规则跑出来的结果如下，只会算出来一个函件。

# A tibble: 4 × 5
# Groups:   customer_id, product [1]
  customer_id product policy_id amount deliver
        <dbl> <chr>       <int>  <dbl> <lgl>  
1           4 A             131     41 FALSE  
2           4 A             132     31 TRUE   
3           4 A             133     21 FALSE  
4           4 A             134     11 FALSE

yuanfan

fenguoerbian

我重新看了下一楼的描述，确实没说清楚问题，容易产生歧义，抱歉，是我的锅。现在我把一楼的描述调整了一下，后来者再看应该不会再掉坑里了吧。

fenguoerbian

yuanfan

这，你把41,11,31,21扔给函数也能得到2封啊……所以，这个问题是不按时间先后顺序的，而是消费记录全拿出来排列组合看最多能有多少封？

现实业务的话，这相当于是每隔一段时间来盘算一下这段时间用户最多能有多少封？毕竟如果这个判断是实时的，那么就是按照时间顺序来了。

而如果这是想排列组合看最多能有多少个合计大于50，那我就想直接猜一个问题本身NP-hard然后躺平不做了……

yuanfan

fenguoerbian

哈哈哈，是啊，这不是按时间顺序来的，是个排列组合问题。嗯，也不是实时的。我在实际计算的时候就是拆出来几种情况，剩下一部分手工算的。

哈哈哈，我搜了一下 NP-hard，没有看懂。不过既然你这么厉害都躺平了，那我也跟着躺平好了。

fenguoerbian

yuanfan

啥是NP-hard我也说不清楚，我只知道这个类型的问题我是断然解不出来的，于是每次碰到排列组合的问题解不出来就会脑子里蹦出这个词……

fenguoerbian

yuanfan

因为平常没有接触到“万元”（捂脸）……

yuanfan

fenguoerbian
O(∩_∩)O哈哈~

俺明白了，这个问题我跟我同事都没想出来什么好的解法，我还以为是我俩笨呢，哈哈哈，这下我可以心安理得地告诉她解不出来不是因为脑子不好使啦。

shrektan

大晚上的，看到这帖子想了下：

题目简化为，把底层表汇总成表DT，字段为购买人、购买产品、购买记录、总金额
构建一个算法no_of_letters(x)，可以根据一个数值向量输出一个list，list的长度就是函件数量，list的内容就是哪几个购买记录对应一个函件
按购买人、购买产品为组别，对总金额的向量应用算法no_of_letters(x)

算法no_of_letters(x):

统计x>=50的个数，每一个记录一个函件
对与x<50的部分的算法，取决于目标是什么，从题主的描述来看，是想最大化函件数量，但不知道有没有直接的算法。最简单的就是先找一个最大的购买记录，再从最小的往上加，加到50了就算一个。再不断重复。这应该不是最优解，但也不是最差的。

上代码：

library(data.table)
data = data.table(
  id = c(1:14),
  customer_id = c(rep(1, 2), rep(2, 3), rep(3, 5), rep(4, 4)),
  policy_id = c(123:124, rep(125, 3), 126:134),
  product = c(rep('A', 2), rep('B', 3), rep('C', 4), 'D', rep('E', 4)),
  fee = c(51, 51, 71, 31, 21, 28, 28, 28, 20, 51, 41, 31, 21, 11))

DT = data[, .(fee = sum(fee), ids = list(id)), keyby = .(customer_id, product, policy_id)]

cal = function(x, ids, out = NULL) {
  # x must be in accending order and all smaller than 50
  # x and ids must share the same length
  v_cumsum = cumsum(x)
  if (length(x) && v_cumsum[length(v_cumsum)] >= 50) {
    v_cumsum2 = v_cumsum + x[length(x)]
    i = which(v_cumsum2 >= 50)[1L]
    i = c(seq_len(i), length(x))
    out = list(unlist(ids[i]))
    ids = ids[-i]
    x = x[-i]
    if (sum(x) >= 50) {
      out = c(out, cal(x, ids))
    } else {
      out
    }
  }
}

no_of_letters = function(x, ids) {
  # x must be accending order
  # ids must be a list with the same length as x
  stopifnot(is.list(ids))
  out = ids[x >= 50]
  ids = ids[x < 50]
  x = x[x < 50]
  c(out, cal(x, ids))
}
# calculate the letter info
setorder(DT, fee)
out = DT[, .(letter_info = no_of_letters(fee, ids)), keyby = .(customer_id, product)]
out[, letter_id := seq_len(.N)]
print(out)
#>    customer_id product letter_info letter_id
#> 1:           1       A           1         1
#> 2:           1       A           2         2
#> 3:           2       B       3,4,5         3
#> 4:           3       C       9,6,8         4
#> 5:           3       D          10         5
#> 6:           4       E       14,11         6
#> 7:           4       E       13,12         7

# merge back to the dataset
out2 = out[, .(id = unlist(letter_info)), keyby = .(customer_id, product, letter_id)]
data = out2[data, on = c("customer_id", "product", "id")]
print(data)
#>     customer_id product letter_id id policy_id fee
#>  1:           1       A         1  1       123  51
#>  2:           1       A         2  2       124  51
#>  3:           2       B         3  3       125  71
#>  4:           2       B         3  4       125  31
#>  5:           2       B         3  5       125  21
#>  6:           3       C         4  6       126  28
#>  7:           3       C        NA  7       127  28
#>  8:           3       C         4  8       128  28
#>  9:           3       C         4  9       129  20
#> 10:           3       D         5 10       130  51
#> 11:           4       E         6 11       131  41
#> 12:           4       E         7 12       132  31
#> 13:           4       E         7 13       133  21
#> 14:           4       E         6 14       134  11

# check the result
data[!is.na(letter_id), .(fee = sum(fee)), keyby = .(customer_id, product, letter_id)] |> print()
#>    customer_id product letter_id fee
#> 1:           1       A         1  51
#> 2:           1       A         2  51
#> 3:           2       B         3 123
#> 4:           3       C         4  76
#> 5:           3       D         5  51
#> 6:           4       E         6  52
#> 7:           4       E         7  52

<sup>Created on 2022-12-05 with reprex v2.0.2</sup>

meeeeeeeeo

这种最多组合数的问题，我觉得能在 leetcode 上找到类似的，虽然我既不会也找不到就是了 😢