大型 R 数据集中子集和问题的变体

Question

我有一个小问题：

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", "D", "B", "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, 80, 70, 120, 100, 50, 10)
)

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 D        10
10     2        80 B        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

如图所示，每一组都有一个阈值，并且有多个id。可以出现超过 1 个 id，但值不同。

目标是选择ids，直到值的总和最接近阈值；因此，与典型的背包问题不同，如果总和值最接近该组的阈值，则所选 id 值的总和可能会超过阈值。

需要注意的是，对于每个组，相同的 id 不能被选择两次。

我正在寻找的解决方案（理想情况下以表格的形式）如下：

solution_tibble
# A tibble: 20 × 4
   group threshold id    value
   <dbl>     <dbl> <chr> <dbl>
 1     1       100 B         5
 2     1       100 A        90
 3     2        80 B         5
 4     2        80 C         1
 5     2        80 D        10
 6     2        80 B        60
 7     3       150 A        10
 8     3       150 B        10
 9     3       150 C        10
10     4       200 A        32
11     4       200 B        70
12     4       200 C       100

现在，这可以通过检查所有幂集及其总和来完成，但问题是我正在处理的实际数据是数十万个组，以及数百万个相应的 id。

我想讨论解决大型数据集的子集和问题变体的最佳方法。

（我目前只设置了贪婪算法，这显然不能保证所选id之和的最优性）

Answer 1

Stack Overflow 问题讨论了针对大型数据集定制的子集和问题的变体。它寻求解决方案来有效地找到满足特定总和条件的子集，同时应对数据大小带来的挑战。