大型 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", "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

如图所示，每一组都有一个阈值，并且有多个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 A        10
 6     2        80 D        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

您可以计算值组组合的

cumsum

，然后使用

subset

计算最小绝对差值

ave

。由于交互组 id 具有空元素（检查

with(sampledf, interaction(group, id))

），这会产生警告，我们可能会抑制该警告。

> sampledf |> within({
+   cum_value <- ave(value, group, id, FUN=cumsum)
+   flag <- as.logical(
+     ave(abs(cum_value - threshold), group, id, FUN=\(x) x == min(x)) |> 
+       suppressWarnings()
+   )
+ }) |> subset(flag, select=-flag)
   group threshold id value cum_value
2      1       100  B     5         5
3      1       100  C    20        20
4      1       100  A    90       100
5      1       100  D    40        40
6      2        80  A    90        90
7      2        80  B     5         5
8      2        80  C     1         1
10     2        80  D    60        60
11     2        80  E    50        50
12     3       150  A    10        10
13     3       150  B    10        10
14     3       150  C    10        10
17     4       200  C   100       100
18     4       200  A   120       152
19     4       200  B    50       120
20     4       200  D    15        15