algorithm - 如何分配存储桶中的元素数以使其在一定范围内-算法

我一直在解决一个问题，假设我有50个元素
n1, n2, n3, ... , n50。
现在我有一个数量有限的桶，比如说5个桶，这个桶可以容纳一个范围，比如说100到150（这只是桶中元素的总和），但是不能少于100，也不能超过150。
哪个算法最适合解决这个问题，这样5个bucket都被使用了，所有元素(n1, n2, n3, ...)也都被用完了。
如果没有使用bucket或者遗漏了任何元素，那么算法只返回“InvalidConditionsFound”。
我试过背包，它给你一个接近给定数字的组合，但如何在一定范围内得到它，并确保它明智地选择，使所有的桶都被填满，而不是两个桶得到150满，另一个桶只有，说50

最佳答案

一种方法是将其建模为整数程序。假设有“m”数字y_1，y_2，…，y_m和“n”桶。定义变量x_i j，每个要分配的数字都有一个索引“i”，每个bucket都有一个索引“j”这些是二进制变量，指示是否将每个数字分配给每个存储桶。
现在有两组逻辑约束。首先，您需要将每个数字恰好分配给一个bucket您可以为每个数字“i”添加以下约束：

x_i1 + x_i2 + ... + x_in = 1

每个bucket“j”也有范围限制：

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

实际上，您只是在寻找任何可行的解决方案，所以您可以将目标设置为0，并将其视为可行性问题。
当你在解决一个np完全问题时，这是一个理论上具有挑战性的练习，你可能会发现现代优化软件可以解决你感兴趣的问题大小。
为了给出可伸缩性的概念，考虑R中使用lpSolve包的以下实现；当存在有效赋值时，它将从数字返回到桶，否则返回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

我用从m中随机抽样的[1, 2, ..., 10]权重、bucket[100, 150]的可接受范围和bucketn = 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（两者一般都是非免费的，但学术使用是免费的）。
以稀疏格式输入约束矩阵。

关于algorithm - 如何分配存储桶中的元素数以使其在一定范围内-算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32964453/