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

      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))

          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

              fenguoerbian

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

                yuanfan

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

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

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

                    fenguoerbian

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

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

                        fenguoerbian

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

                            yuanfan

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

                                fenguoerbian
                                O(∩_∩)O哈哈~

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

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

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

                                  算法no_of_letters(x):

                                  1. 统计x>=50的个数，每一个记录一个函件
                                  2. 对与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>

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