R：在朋友组中最佳地共享 Cookie

Question

我正在使用 R 编程语言。

假设有 100 人 - 每个人都用 1:100 开始的 ID 表示。每个人都可以与其他人成为朋友。数据集可以用图形/网络格式表示，如下所示：

# Set the seed for reproducibility
set.seed(123)

# Generate a vector of ID's from 1 to 100
ids <- 1:100

# Initialize an empty data frame to store the "from" and "to" values
edges <- data.frame(from=integer(), to=integer(), stringsAsFactors=FALSE)

# Iterate through the ID's
for(id in ids) {
    # Randomly select a minimum of 1 and a maximum of 8 neighbors for the current ID
    neighbors <- sample(ids[ids != id], size=sample(1:8, size=1))
    
    # Add a new row to the data frame for each "to" value
    for(neighbor in neighbors) {
        edges <- rbind(edges, data.frame(from=id, to=neighbor))
    }
}

正如我们所看到的，数据可以可视化以揭示图形/网络格式：

library(igraph)
library(visNetwork)


# Convert the data frame to an igraph object
g <- graph_from_data_frame(edges, directed=FALSE)

# Plot the graph
plot(g)

# Optional visualization
#visIgraph(g)

现在，假设该数据集中的每个人都有一定数量的 cookie。这看起来像这样：

set.seed(123)

cookies = data.frame(id = 1:100, number_of_cookies = c(abs(as.integer(rnorm(25, 15, 5))), abs(as.integer(rnorm(75, 5, 5)))))
                 

这是我的问题：

• 我想确保这个数据集中没有人拥有少于 12 个 cookie - 也就是说，如果某人拥有少于 12 个 cookie，他们可以将他们的 cookie 与邻居（例如一级邻居、二级邻居）“汇集”在一起, ... n 级邻居 ... 直到满足这个条件），看看他们现在是否有超过 12 个 cookie
• 但是，我还想确保在此池化过程中，池化的朋友组中没有超过 20 个 cookie（即，这可能需要“取消池化”之前池化在一起的邻居）
• 最后，如果某人与其他人在一个组中 - 那么这个人不能被放入另一个组中（即没有“双重浸入”）

我编写了一个函数，它接受一个 ID 作为输入，然后返回该 ID 以及该 ID 的所有邻居的 cookie 总数：

library(data.table)
library(dplyr)


sum_cookies_for_id <- function(id) {
    
    # Get the connected IDs for the given ID
    connected_ids <- c(id, edges[edges$from == id | edges$to == id, "to"])
    
    # Sum the number of cookies for all connected IDs
    sum(cookies[cookies$id %in% connected_ids, "number_of_cookies"])
}

# Test the function
sum_cookies_for_id(23)

但除此之外，我不知道如何继续。

有人可以告诉我如何继续为这个问题编写代码吗？在这样的例子中可以使用动态规划吗？

谢谢！

注意事项：

• 我认为这个问题可能具有“随机”性质 - 也就是说，取决于您从哪个 ID 开始以及您将此特定 ID 与哪个其他 ID 分组......最终可能会导致更少或更多的人拥有少于 12 个 cookie
• 我认为编写一个执行随机分组的“贪婪”算法可能是解决此类问题的最简单选择？
• 将来，我有兴趣了解如何使用更“复杂的算法”（例如遗传算法）进行分组，以便留下少于 12 块 cookie 的最少人数。
• 思考：在考虑这些总/总和约束的同时（例如Louvain社区检测），是否有可能使用一些预先存在的图/网络聚类算法来解决这个问题？