如何分配桶中的元素数量以使其在一个范围内 - 算法

Question

我一直在解决一个问题，假设我有 50 个元素 n1, n2, n3, ... , n50.

现在我的桶数量有限，比如 5 个桶，桶可以容纳的范围从 100 到 150（这不过是那个桶中元素的总和），但不少于 100 , 不超过 150.

哪种算法最适合解决这个问题，使得5个桶都用完，元素(n1, n2, n3, ...)也用完

如果不使用桶或遗漏任何元素，则算法只是 returns "InvalidConditionsFound".

我试过 Knapsack，它给你一个接近给定数字的组合，但如何让它在一个范围内，并确保它明智地选择，这样所有的桶都被填满，而不是那两个桶满了 150 而另一个桶只有 50

Answer 1

一种方法是将其建模为整数程序。假设有 "m" 个数字 y_1、y_2、...、y_m 和 "n" 个存储桶。定义变量 x_ij，为您尝试分配的每个数字使用索引 "i"，为每个存储桶使用索引 "j"。这些是二进制变量，指示每个数字是否分配给每个桶。

现在你有两组逻辑约束。首先，您需要将每个数字准确分配给一个桶。您可以通过为每个数字添加以下约束来做到这一点 "i":

x_i1 + x_i2 + ... + x_in = 1

你也有每个桶的范围限制"j":

100 <= y_1 x_1j + y_2 x_2j + ... + y_m x_mj <= 150

实际上你只是在寻找任何可行的解决方案，所以你可以将 objective 设置为 0 并将其视为可行性问题。

虽然您正在解决 NP 完全问题，因此这是一个理论上具有挑战性的练习，但您可能会发现现代优化软件可以解决您感兴趣的问题规模的问题。

为了了解可扩展性，请考虑以下使用 R 中的 lpSolve 包的实现；它 returns 当存在有效分配时从数字到桶的分配，否则 returns NA 值的向量：

library(lpSolve)
range.assign <- function(weights, n, min.sum, max.sum) {
  m <- length(weights)
  one.mat <- t(sapply(1:m, function(i) c(replicate(n, 1*((1:m) == i)))))
  w.mat <- t(sapply(1:n, function(j) c(rep(0, m*(j-1)), weights, rep(0, m*(n-j)))))
  mod <- lp(objective.in = rep(0, n*m),
            const.mat = rbind(one.mat, w.mat, w.mat),
            const.dir = rep(c("=", ">=", "<="), c(m, n, n)),
            const.rhs = rep(c(1, min.sum, max.sum), c(m, n, n)),
            all.bin=TRUE)
  if (mod$status == 0) {
    apply(matrix(mod$solution, nrow=m), 1, function(x) which(x >= 0.999))
  } else {
    rep(NA, m)
  }
}
range.assign(1:5, 2, 5, 10)
# [1] 1 1 1 1 2
range.assign(1:5, 2, 5, 6)
# [1] NA NA NA NA NA

我使用从 [1, 2, ..., 10] 中随机抽取的 m 个权重、桶的可接受范围 [100, 150] 和桶总数 n = ceiling(5.5*m / 125) 进行了测试。我看到了以下运行时缩放：

m = 100, n = 5: 0.1 秒
m = 200, n = 9: 0.6 秒
m = 300, n = 14: 2.2 秒
m = 400, n = 18: 16.9 秒

对于有十几个桶和几百个权重（以及这个权重向量结构）的问题，似乎可以使用免费求解器准确地解决这个问题。当然，您的复杂性结果表明它无法有效解决巨大的问题，但您可以解决您感兴趣的大小的实例。通过以下方式可以进一步优化：

使用 Gurobi 或 cplex 等商业求解器（两者通常都是非免费的，但对于学术用途是免费的）。
正在以稀疏格式输入约束矩阵。

Answer 2

听起来像是一个 k-partitioning 问题，通常被称为 bin-packing problem. 因为这个问题是 NP-Complete，所以不会有 'efficient' 解决方案。但是，如果您在互联网上四处看看，我相信您可以找到大量的代码示例，这样您和您的 (*咳咳*) "collegues" 就可以解决这个问题。

如何分配桶中的元素数量以使其在一个范围内 - 算法

How to distribute the number of elements in a bucket so that it is Within a Range - Algorithm

algorithm

optimization

knapsack-problem

mathematical-optimization

np