大规模R数据集带选择约束的子集和问题最优解法问询

数据集 #

sample_tibble <- tibble(
    group = c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4),
    threshold = c(100, 100, 100, 100, 100, 80, 80, 80, 80, 80, 80, 150, 150, 150, 200, 200, 200, 200, 200, 200),
    id = c("A", "B", "C", "A", "D", "A", "B", "C", "A", "D", "E", "A", "B", "C", "A", "B", "C", "A", "B", "D"),
    value = c(10, 5, 20, 90, 40, 90, 5, 1, 10, 60, 50, 10, 10, 10, 32, 70, 100, 120, 50, 15)
)

sample_tibble
# A tibble: 20 × 4
   group threshold id    value
   <dbl>     <dbl> <chr> <dbl>
 1     1       100 A        10
 2     1       100 B         5
 3     1       100 C        20
 4     1       100 A        90
 5     1       100 D        40
 6     2        80 A        90
 7     2        80 B         5
 8     2        80 C         1
 9     2        80 A        10
10     2        80 D        60
11     2        80 E        50
12     3       150 A        10
13     3       150 B        10
14     3       150 C        10
15     4       200 A        32
16     4       200 B        70
17     4       200 C       100
18     4       200 A       120
19     4       200 B        50
20     4       200 D        15

核心需求 #

• 每个group对应唯一的threshold，需为每个组选择不重复的id（每个id最多选一次，可挑选该id对应的任意一个value）
• 目标：让选中id的value总和最接近对应group的threshold（总和允许超过阈值）
• 当前仅实现贪心算法，但无法保证解的最优性
• 实际数据规模：包含数十万group、数百万条id记录

寻求最优解法 #

需要适配上述大规模数据集的最优解决方案，确保每个group都能得到最接近阈值的id组合。

内容的提问来源于stack exchange，提问作者raven